Hlavní strana   Blog   Práce   Kontakty   Mapa stránek   Filmy  

Podkategorie

C++
Php
Java
JavaScript
Ruby on Rails
Vývoj pro iPhone
Databáze
OpenGL
Hardware
Software
Algoritmy
Technologie
Webdesign
Bezpečnost
Elektronika
Konference
VlastnÍ projekty
Jen tak mimochodem
Hry

Můžete mě sledovat:

          

Projekty

      

Novinky

Nové články
Nějakou dobu jsem psal blog na živě.cz a tomuto blogu se nevěnoval. Během několika dalších dnů budu některé články z blogu na živě.cz přesouvat sem, na tento blog. Bude se jednat hlavně o články, které obsahují zdrojové kódy, protože na živě není implementováno žádné rozšíření pro psaní kódu do článku.

Linkuj a TopClanky
Přidal jsem ke článkům odkazy na Linkuj.cz a TopClanky.cz. Pokud se vám článek líbí, tak to dejte najevo jeho zalinkováním.

Registrace
Dnes, 13.září, byla přídána možnost registrace.

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

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);
	}
}

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");
}

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 . '
';
    }
 }
 
 $string = 'abc';
 $num = 2;
 new chars_combination( $string, $num );