Generator słów - metoda własna

Autor: Adrian Adamczyk

Zachęcam do czytania wersji pdf, dostępnej w załączniku.

O algorytmie

Zadaniem algorytmu jest znalezienie kolejnej kombinacji znaków na podstawie obecnego zestawu, lub takowego rozpoczęcie. Kolejna kombinacja zwracana jest za każdym wywołaniem funkcji.

Wejście algorytmu

Na wejściu algorytmu należy podać tablicę znaków, jakie będą używane do generowania kombinacji, oraz maksymalną długość wygenerowanego słowa. Dodatkowym parametrem może być słowo od którego wznawiamy generowanie.
Przykładowa tablica znaków: 0123456789 abcdefghijklmnopqrstuvwxyz
Przykładowa maksymalna długość słowa: 8
Przykładowy dodatkowy parametr: aaaadfgh

Wyjście algorytmu

Za każdym wywołaniem funkcji generującej otrzymujemy kolejną kombinację znaków, obliczoną na podstawie danych wejściowych.
Przykładowe kolejne wyjścia:
aaa, aab, aac, aad, aaf, .., zzx, zzy, zzz

Sposób działania

Załóżmy, że na wejściu mamy daną tablicę małych znaków alfabetu łacińskiego: abcdefghijklmnopqrstuvwxyz, oraz maksymalną długość hasła równą 6.
Realizacja naszego algorytmu odbędzie się za pomocą dwóch funkcji – jednej głównej o nazwie nastepnaKombinacja() oraz drugiej rekurencyjnej* – przeskocz(). Na początku należy utworzyć tablicę o nazwie obecnaKombinacja z rozmiarem równym maksymalnej długości hasła, i każde pole wypełnić wartością -1. Taka wartość będzie dla nas oznaczać, że w tym miejscu nie ma jeszcze żadnego znaku.

Nr. elementu	0	1	2	3	4	5
Wartość	-1	-1	-1	-1	-1	-1
Druga tablica o nazwie tablicaZnakow będzie przyporządkowywała kolejne numery kolejnym znakom tablicy znaków:
0	1	2	3	4	5	6
----------------	----------------	----------------	----------------	----------------	----------------	----------------
a	b	c	d	e	f	g

Tabela ta przechowuje obecną kombinację, a sposób jej odczytywania jest następujący:

1)     i := 0
2)     dopóki i < maksymalnaDlugoscHasla
2.1)     i := i + 1
2.2)     jeżeli obecnaKombinacja[i] <> -1 to:
2.2.1)      dopisz znak tablicaZnakow[obecnaKombinacja[i]] na wyjście
3)     koniec.

Działanie funkcji nastepnaKombinacja() polega na odczytaniu tablicy obecnaKombinacja w w/w zdefiniowany sposób, oraz wywołanie funkcji przeskocz() która w funkcji nastepnaKombinacja() zawsze przyjmie parametr równy maksymalnaDlugoscSlowa-1.

Celem rekurencyjnej funkcji przeskocz() jest zwiększenie określonego w parametrze funkcji pola tablicy obecnaKombinacja o 1, a gdy zwiększona wartość jest równa długości tablicy tablicaZnakow należy pole wyzerować, a następnie wywołać funkcję rekurencyjnie* z poprzednim parametrem o 1 mniejszym.

Łatwo można sobie to wyobrazić, że gdy w momencie zwiększania ostatniego pola wyjdziemy poza zakres tablicy tablicaZnakow, należy zacząć na obecnym polu zwiększanie od początku, oraz pociągnąć za sobą zwiększenie wartości na polu przedostatnim. Jeżeli taka sama sytuacja zdarzy się na polu przed ostatnim, pociągnie to znowu za sobą zwiększenie wartości 3 pola od końca.

Jeżeli po wykonaniu funkcji przeskocz() pierwszy element tablicy obecnaKombinacja przyjmie ostatni znak z tablicy tablicaZnakow, otrzymaliśmy ostatnią możliwą kombinację.

Funkcję przeskocz() która przyjmuje jeden parametr o umownej nazwie pozycja można zdefiniować następująco:

1)     obecnaKombinacja[pozycja] := obecnaKombinacja[pozycja]+1
2)     jeżeli obecnaKombinacja[pozycja] = rozmiarTablicyZnakow
2.1)         obecnaKombinacja[pozycja] := 0
2.2)         przeskocz(pozycja-1)
3)     koniec.

Przykładowa implementacja z testem wydajnowym: Java

package generatorslow;

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class GeneratorSlow
{
    private final String listaZnakow;
    private final int dlugosc;
    private final int iloscZnakow;
    private int[] status;
    private boolean koniec;
    
    public GeneratorSlow(String znaki, int dl)
    {
        listaZnakow = znaki;
        koniec = false;
        dlugosc = dl;
        iloscZnakow = znaki.length();
        status = new int[dlugosc];
        
        for (int i = 0; i < dlugosc; i++)
            status[i] = -1;
    }
    
    public GeneratorSlow(String znaki, int dl, String zacznijOd)
    {
        listaZnakow = znaki;
        iloscZnakow = znaki.length();
        dlugosc = dl;
        status = new int[dlugosc];     
        
		// Wypełniamy tablicę status podanym słowem, np. aabbccdd. Wada na razie jest taka, że długość zacznijOd == dlugosc
        for (int i = 0; i < dlugosc; i++)
            for (int x = 0; x < iloscZnakow; x++)
                if (listaZnakow.charAt(x) == zacznijOd.charAt(i))
                    status[i] = x;
    }
        
    public String nastepnaKombinacja()
    {
        if (status[0] != iloscZnakow-1)
            przeskocz(dlugosc-1);
        else
            koniec = true;
        
        return odczytajKombinacje();
    }
    
    public boolean czyKoniec()
    {
        return koniec;
    }
    
    private String odczytajKombinacje()
    {
        String nowaKombinacja = "";
        
        for (int i = 0; i < dlugosc; i++)
            if (status[i] != -1)
                nowaKombinacja += listaZnakow.charAt(status[i]);
        
        return nowaKombinacja;
    }
    
    private void przeskocz(int pozycja)
    {
        status[pozycja]++;
        
        if (status[pozycja] == iloscZnakow)
        {
            status[pozycja] = 0;
            
            przeskocz(pozycja-1);
        }
    }
    
    public static void main(String[] args)
    {
        String tablicaZnakow = "0123456789abcdefghijklmnopqrstuvwxyz";
        GeneratorSlow generatorSlow = new GeneratorSlow(tablicaZnakow, 8);
        
        long i = 0;
        String kombinacja;
        long czas = System.currentTimeMillis();
        
        while (!generatorSlow.czyKoniec())
        {
            kombinacja = generatorSlow.nastepnaKombinacja();
            
            i++;
            
			// Tutaj wypisujemy co milionową kombinację i ilość generowanych kombinacji/s
            if (i % 1000000 == 0)
                System.out.println(i/1000000 + "kk) " + kombinacja + "  " + ((((System.currentTimeMillis()-czas)/1000) == 0) ? "" : i/((System.currentTimeMillis()-czas)/1000)) + "/s (" + (System.currentTimeMillis()-czas)/1000 + "s)");
           
        }
        
        System.out.println("Koniec.");
    }
}