Abecední kombinace znaků (Java/C/PHP)

Jednoduchý algoritmus na vytvoření kombinace zadaných znaků o zadané délce výsledného řetězce.

Pro různé potřeby testování řetězců můžete někdy potřebovat postupně generovat ze vstupních zadaných znaků všechny jejich kombinace.

Uvedu na příkladu:

Mám zadány znaky AB a chci pro ně generovat všechny různé kombinace o délce 4 znaků.

Potřebuji dosáhnout tohoto výsledku:

AAAA
AAAB
AABA
AABB
ABAA
ABAB
ABBA
ABBB
BAAA
BAAB
BABA
BABB
BBAA
BBAB
BBBA
BBBB

AAAA

AAAB

AABA

AABB

ABAA

ABAB

ABBA

ABBB

BAAA

BAAB

BABA

BABB

BBAA

BBAB

BBBA

BBBB

Algoritmus funguje tak, že si nejprve ze vstupního řetězce(znaky z nichž se kombinace generují) vytvoří pole. Pole obsahuje tolik prvků, kolik je znaků v řetězci.

Stejně tak si vytvoří druhé pole, které obsahuje tolik prvků, kolik je požadovaných znaků v kombinacích. Hodnoty tohoto pole budou reprezentovat indexy v prvním poli, které budou značit znaky.

Na začátku nastavíme hodnoty pole indexů na 0, abychom dosáhli první kombinaci, čili kombinaci pouze prvních znaků ze vstupního řetězce.

Ve funkci budeme neustále měnit indexy tohoto pole a zvyšovat je až do velikosti pole znaků. Potom přejdeme na vedlejší index vlevo.

Vždy po zvětšení každého indexu musíme začít rekurzivně měnit indexy v pravé části od námi měněného indexu a to od konce pole.

Lepší pochopení bude z programu, který by šel řešit jednodušeji bez pole indexů, ovšem tento způsob je přehlednější.

Zdrojový kód v Javě:

public class chars_combination {

	private String[] chars;;

	private int num;

	private int[] position;

	public chars_combination(String string, int num) {
		if (string.length() == 0)
			return;
		if (num <= 0)
			return;
		//vytvori se pole znaku pro kombinace              
		this.chars = new String[string.length()];
		for (int i = 0; i < string.length(); i++) {
			this.chars[i] = string.substring(i, i + 1);
		}

		this.num = num;
		this.create_array();
		this.return_string(this.position);

		//maximalni index         
		int max = this.chars.length - 1;
		//pocatecni index v poli indexu
		int id = this.position.length - 1;

		this.make_indexes(this.position, max, id, 0);
	}

	private void create_array() {
		this.position = new int[this.num];
		for (int i = 0; i < this.num; i++) {
			this.position[i] = 0;
		}
	}

	public void make_indexes(int[] array, int max, int pos, int limit) {
		//pokud je pozice v poli rovna nule, rekurze konci
		if (pos < limit || array[pos] >= max)
			return;

		//zvysime hodnotu indexu o 1
		array[pos] = array[pos] + 1;

		//funkce pro zpracovani pole indexu
		this.return_string(array);

		//pokud je upravovan index mensi nez pozice, musi se rekurzivne zvysovat prava strana pole.                      
		if (pos + 1 < array.length) {
			//rekurzivne se vola funkce
			this.make_indexes(array, max, array.length - 1, pos + 1);
		}
		//pokud je hodnota vetsi nez maximalni, snizi se index a hodnota aktualniho prvku se zmensi na nulu. 
		if (array[pos] >= max) {
			array[pos] = 0;
			--pos;
		}

		//rekurzivne se vola dalsi cyklus funkce. 
		this.make_indexes(array, max, pos, limit);
	}

	public void return_string(int[] array) {
		String string = "";
		for (int i = 0; i < array.length; i++) {
			string += this.chars[array[i]];
		}
		//vypis kombinace
		System.out.println(string);
	}

	public static void main(String[] args) {
		new chars_combination("AB", 4);
	}
}

public class chars_combination {

private String[] chars;;

private int num;

private int[] position;

public chars_combination(String string, int num) {

if (string.length() == 0)

return;

if (num <= 0)

return;

//vytvori se pole znaku pro kombinace

this.chars = new String[string.length()];

for (int i = 0; i < string.length(); i++) {

this.chars[i] = string.substring(i, i + 1);

}

this.num = num;

this.create_array();

this.return_string(this.position);

//maximalni index

int max = this.chars.length - 1;

//pocatecni index v poli indexu

int id = this.position.length - 1;

this.make_indexes(this.position, max, id, 0);

}

private void create_array() {

this.position = new int[this.num];

for (int i = 0; i < this.num; i++) {

this.position[i] = 0;

}

public void make_indexes(int[] array, int max, int pos, int limit) {

//pokud je pozice v poli rovna nule, rekurze konci

if (pos < limit || array[pos] >= max)

return;

//zvysime hodnotu indexu o 1

array[pos] = array[pos] + 1;

//funkce pro zpracovani pole indexu

this.return_string(array);

//pokud je upravovan index mensi nez pozice, musi se rekurzivne zvysovat prava strana pole.

if (pos + 1 < array.length) {

//rekurzivne se vola funkce

this.make_indexes(array, max, array.length - 1, pos + 1);

}

//pokud je hodnota vetsi nez maximalni, snizi se index a hodnota aktualniho prvku se zmensi na nulu.

if (array[pos] >= max) {

array[pos] = 0;

--pos;

}

//rekurzivne se vola dalsi cyklus funkce.

this.make_indexes(array, max, pos, limit);

}

public void return_string(int[] array) {

String string = "";

for (int i = 0; i < array.length; i++) {

string += this.chars[array[i]];

}

//vypis kombinace

System.out.println(string);

}

public static void main(String[] args) {

new chars_combination("AB", 4);

}

Zdrojový kód v Céčku:

//definice funkci
void create_combination( char *input_string, int num );
void create_array( int *num, int *positions );
void make_indexes( int * array, int max, int pos, int limit);
void return_string( int * array );

//globalni promenne
int num_of_positions = 0;
char * used_chars;

//main
int main(int argc, char *argv[])
{
    //vstupni retezec
    char *input_string = "abcdefghijklmnopqrstuvwxyz";
    //pocet znaku v kombinacich
    int num = 3;
    
    //jednoducha kontrola
    if( strlen( input_string ) == 0 ){
        return EXIT_SUCCESS;
    }
    if( num <= 0 ){
        return EXIT_SUCCESS;
    }
    
    create_combination( input_string, num );
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

void create_combination( char *input_string, int num ){

     //vytvoreni pole znaku
     char chars[ strlen( input_string )];
     for( int i = 0; i < strlen( input_string ); i++ ){
          chars[i] = input_string[i];
     }              
     
     //nastaveni globalnich promennych
     used_chars = chars;
     num_of_positions = num;
     
     //vytvoreni prazdneho pole indexu
     int positions[num];
     create_array( & num, positions );
     
     //nastaveni maximalniho indexu
     int max = sizeof(chars) - 1;
     
     //nastaveni pocatecniho indexu v poli indexu
     int id = num - 1;
     
     //vraceni prvni kombinace
     return_string( positions );
     //generovani dalsich kombinaci
     make_indexes(positions, max, id, 0 );
}

//vytvoreni pole indexu - naplni hodnotami 0
void create_array( int *num, int * positions ){
     for( int i = 0; i < *num; i++ ){
          positions[i] = 0;      
     } 
}

//generuje indexy kombinaci 
void make_indexes( int * array, int max, int pos, int limit){
     //pokud je pozice mensi nez limit - konec
     if( pos < limit || array[pos] >= max )
         return;
         
     //pripocitani hodnoty 1 k indexu
     array[pos] = array[pos] + 1;
     
     //zpracuje indexy
     return_string(array);
     
     //rekurzivne dopocita indexy na prave strane retezce. 
     if( ( pos + 1 ) < sizeof( array ) ){
         make_indexes( array, max, num_of_positions - 1, pos + 1 );  
     }
     
     //pokud je hodnota indexu vetsi nez maximalni, posune se doprava
     if( array[pos] >= max ){
         array[pos] = 0;
         --pos;    
     }
     //rekurzivne vola pro dalsi index
     make_indexes( array, max, pos, limit);
}

//zpracovani retezce
void return_string( int * array ){
     for( int i = 0; i < num_of_positions; i++ ){
          printf("%c", used_chars[ array[i] ]);
     }     
     printf("n");
}

100

//definice funkci

void create_combination( char *input_string, int num );

void create_array( int *num, int *positions );

void make_indexes( int * array, int max, int pos, int limit);

void return_string( int * array );

//globalni promenne

int num_of_positions = 0;

char * used_chars;

//main

int main(int argc, char *argv[])

{

//vstupni retezec

char *input_string = "abcdefghijklmnopqrstuvwxyz";

//pocet znaku v kombinacich

int num = 3;

//jednoducha kontrola

if( strlen( input_string ) == 0 ){

return EXIT_SUCCESS;

}

if( num <= 0 ){

return EXIT_SUCCESS;

}

create_combination( input_string, num );

system("PAUSE");

return EXIT_SUCCESS;

}

void create_combination( char *input_string, int num ){

//vytvoreni pole znaku

char chars[ strlen( input_string )];

for( int i = 0; i < strlen( input_string ); i++ ){

chars[i] = input_string[i];

}

//nastaveni globalnich promennych

used_chars = chars;

num_of_positions = num;

//vytvoreni prazdneho pole indexu

int positions[num];

create_array( & num, positions );

//nastaveni maximalniho indexu

int max = sizeof(chars) - 1;

//nastaveni pocatecniho indexu v poli indexu

int id = num - 1;

//vraceni prvni kombinace

return_string( positions );

//generovani dalsich kombinaci

make_indexes(positions, max, id, 0 );

}

//vytvoreni pole indexu - naplni hodnotami 0

void create_array( int *num, int * positions ){

for( int i = 0; i < *num; i++ ){

positions[i] = 0;

}

//generuje indexy kombinaci

void make_indexes( int * array, int max, int pos, int limit){

//pokud je pozice mensi nez limit - konec

if( pos < limit || array[pos] >= max )

return;

//pripocitani hodnoty 1 k indexu

array[pos] = array[pos] + 1;

//zpracuje indexy

return_string(array);

//rekurzivne dopocita indexy na prave strane retezce.

if( ( pos + 1 ) < sizeof( array ) ){

make_indexes( array, max, num_of_positions - 1, pos + 1 );

}

//pokud je hodnota indexu vetsi nez maximalni, posune se doprava

if( array[pos] >= max ){

array[pos] = 0;

--pos;

}

//rekurzivne vola pro dalsi index

make_indexes( array, max, pos, limit);

}

//zpracovani retezce

void return_string( int * array ){

for( int i = 0; i < num_of_positions; i++ ){

printf("%c", used_chars[ array[i] ]);

}

printf("n");

}

Zdrojový kód v PHP:

 class chars_combination{
    
     private $chars = array();
     private $num;
     private $position = array();
     /**
    * konstruktor tridy. 
    * param $string - mozne znaky pro kombinace
    * param $num    - pocet znaku v kombinacich   
    */
    function __construct( $string, $num ){
        if( strlen( $string ) == 0 )
            return;
        if( intval( $num  ) <= 0 )
            return;
        
        //vytvori se pole znaku pro kombinace    
        for( $i = 0; $i < strlen( $string ); $i++ ){
            $this->chars[] = $string[$i];   
        }

        $this->num = intval( $num );
        self::_create_array();
        
        self::_return_string( $this->position );
        //maximalni index
        $max = count( $this->chars ) - 1;
        //pocatecni index v poli indexu
        $id = count( $this->position ) - 1 ;         
        
        self::make_indexs( $this->position, $max, $id, 0);
    }   
    
    /**
    * funkce vytvori prazne pole, reprezentujici indexy v poli znaku. 
    */
    private function _create_array(){
        for( $i = 0; $i < $this->num; $i++ ){
            $this->position[] = 0;   
        }
    }
    
    private function make_indexs( $array, $max, $pos, $limit ){
        //pokud je pozice v poli rovna nule, rekurze konci
        if( $pos < $limit || $array[$pos ] >= $max )
            return; 
        
        //zvysime hodnotu indexu o 1
        $array[$pos] = $array[$pos] + 1;
        
        //funkce pro zpracovani pole indexu
        self::_return_string( $array );
                      
        //pokud je upravovan index mensi nez pozice, musi se rekurzivne zvysovat prava strana pole.                      
        if( $pos + 1 < count( $array )){
            //rekurzivne se vola funkce
            self::make_indexs( $array, $max, count( $array ) - 1, $pos + 1);
        }
        //pokud je hodnota vetsi nez maximalni, snizi se index a hodnota aktualniho prvku se zmensi na nulu. 
        if( $array[ $pos ] >= $max ){
            $array[$pos] = 0;
            --$pos;
        }
        
        //rekurzivne se vola dalsi cyklus funkce. 
        self::make_indexs( $array, $max, $pos, $limit );
    }
    
    
    //funkce pro spracovani
    public function _return_string( $array ){
        $string = null;
        for( $i = 0; $i < count( $array ); $i++ ){
            $string .= $this->chars[$array[$i]];
        }
        //vypis kombinace
        print $string . '<br />';
    }
 }
 
 $string = 'abc';
 $num = 2;
 new chars_combination( $string, $num );

class chars_combination{

private $chars = array();

private $num;

private $position = array();

/**

* konstruktor tridy.

* param $string - mozne znaky pro kombinace

* param $num - pocet znaku v kombinacich

function __construct( $string, $num ){

if( strlen( $string ) == 0 )

return;

if( intval( $num ) <= 0 )

return;

//vytvori se pole znaku pro kombinace

for( $i = 0; $i < strlen( $string ); $i++ ){

$this->chars[] = $string[$i];

}

$this->num = intval( $num );

self::_create_array();

self::_return_string( $this->position );

//maximalni index

$max = count( $this->chars ) - 1;

//pocatecni index v poli indexu

$id = count( $this->position ) - 1 ;

self::make_indexs( $this->position, $max, $id, 0);

}

/**

* funkce vytvori prazne pole, reprezentujici indexy v poli znaku.

private function _create_array(){

for( $i = 0; $i < $this->num; $i++ ){

$this->position[] = 0;

}

private function make_indexs( $array, $max, $pos, $limit ){

//pokud je pozice v poli rovna nule, rekurze konci

if( $pos < $limit || $array[$pos ] >= $max )

return;

//zvysime hodnotu indexu o 1

$array[$pos] = $array[$pos] + 1;

//funkce pro zpracovani pole indexu

self::_return_string( $array );

//pokud je upravovan index mensi nez pozice, musi se rekurzivne zvysovat prava strana pole.

if( $pos + 1 < count( $array )){

//rekurzivne se vola funkce

self::make_indexs( $array, $max, count( $array ) - 1, $pos + 1);

}

//pokud je hodnota vetsi nez maximalni, snizi se index a hodnota aktualniho prvku se zmensi na nulu.

if( $array[ $pos ] >= $max ){

$array[$pos] = 0;

--$pos;

}

//rekurzivne se vola dalsi cyklus funkce.

self::make_indexs( $array, $max, $pos, $limit );

}

//funkce pro spracovani

public function _return_string( $array ){

$string = null;

for( $i = 0; $i < count( $array ); $i++ ){

$string .= $this->chars[$array[$i]];

}

//vypis kombinace

print $string . '<br />';

}

$string = 'abc';

$num = 2;

new chars_combination( $string, $num );

Comments are closed for this page

simon

20/05/2008

Děkuji za článek, zajímavé je různé pojeti v ruznych jazycich. Urcite by se ale hodilo i srovnani rychlosti skriptu. Dale by chtelo vice zminit vyuziti, nejak jsem nepochopil k cemu mi to nekdy bude dobre.

Marek J.

20/05/2008

Tohle se mi zrovna hodi k vytvoreni MD5 crackeru, kde jsem potreboval generovat postupne vsechny mozne kombinace, aby jsem mohl porovnavat jejich hashe. diky

naniccz

20/05/2008

Nebylo by to snazší rekurzí na 10 řádků? 😉

zaachi

20/05/2008

Tak nevím jestli jsi to četl, protože je to řešeno rekurzí.
Ten kód kolem je jenom pro připravení proměnných. Je to schválně rozepsané, aby to bylo pochopitelnější, jak jsem napsal i v textu.

Jakub Vrána

20/05/2008

Viz také http://php.vrana.cz/permutace.php