[PHP] Permutacja ze zbioru bez powtórzeń, gdzie błąd? Opcje

[Aztech]

Witam serdecznie. Chciałem stworzyć sobie klasę, która będzie mi generowała losową próbkę spośród zestawu liter.
Następnie dla tak wygenerowanej próbki znajduje wszystkie wariacje (permutacje) bez powtórzeń.
Np dla wylosowanego zbioru licz:
A,B,C
ma zwrócić:
A,B,C
A,C,B
B,A,C
B,C,A
C,A,B
C,B,A
ale dla zbioru: A,B,A
ma już zwrócić
A,A,B
A,B,A
B,A,A
Poniżej znajdziecie klasę, która działa "prawie" dobrze. Niestety jak to bywa, prawie robi różnicę (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)
Zwraca mianowicie dla zestawu A,B,C
A,B,C
B,A,C
C,A,B
czyli zwraca pierwszą znalezioną kombinację, zaczynającą się kolejno od litery:A, następnie od B, a następnie od C
Poniżej klasa i jej wywołanie:
wywołanie

[PHP] pobierz, plaintext 
<?php
$lvs=new LswVarSet();
$lvs->buildWordSetNoRepeat($lvs->draw(3),3)
?>
[PHP] pobierz, plaintext 

klasa

[PHP] pobierz, plaintext 
<?php
class LswVarSet
  {
 
	private static $SCR_LETTER_SET = array (
	  'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'Ą',
	  'B', 'B', 'C', 'C', 'C', 'Ć', 'D', 'D', 'D', 'E',
	  'E', 'E', 'E', 'E', 'E', 'E', 'Ę', 'F', 'G', 'G',
	  'H', 'H', 'I', 'I', 'I', 'I', 'I', 'I', 'I', 'I',
	  'J', 'J', 'K', 'K', 'K', 'L', 'L', 'L', 'Ł', 'Ł',
	  'M', 'M', 'M', 'N', 'N', 'N', 'N', 'N', 'Ń', 'O',
	  'O', 'O', 'O', 'O', 'O', 'Ó', 'P', 'P', 'P', 'R',
	  'R', 'R', 'R', 'S', 'S', 'S', 'S', 'Ś', 'T', 'T', 
	  'T', 'U', 'U', 'W', 'W', 'W', 'W', 'Y', 'Y', 'Y',
	  'Y', 'Z', 'Z', 'Z', 'Z', 'Z', 'Ź', 'Ż',
	);
 
	private static $SCR_VOWEL = array (
	  'A', 'Ą', 'E', 'Ę', 'I', 'O', 'Ó', 'U', 'Y' 
	);
 
	private static $SCR_CONSONANT = array (
	  'B', 'C', 'Ć', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 
	  'Ł', 'M', 'N', 'P', 'R', 'S', 'Ś', 'T', 'W', 'Z',
	  'Ż', 'Ź'
	);
 
	/**
	 * Check if letter is vowel or not
	 * 
	 * @return boolean true if is vowel
	 */
	public function isVowel($letter)
	{
	  return in_array($letter,self::$SCR_VOWEL);
	}
 
	/**
	 * Check if letter is consonant or not
	 * 
	 * @return boolean true if is consonant
	 */
	public function isConsonant($letter)
	{
	  return in_array($letter,self::$SCR_CONSONANT);
	}
 
	/**
	 * Draws from set of letter using {@param $sampleLength} letters
	 * @return arrat set of letters 
	 */
	public function draw($sampleLength)
	{
	  $draw=array_rand(self::$SCR_LETTER_SET,$sampleLength);
	  foreach ($draw as $key)
		$return[]=self::$SCR_LETTER_SET[$key];
	  return $return;
	}
 
 
	/**
	 * Build set of letter using (@param $num} letters
	 * Set of letter is a permutation without repetition
	 * 
	 * @return list of potential words
	 */
	public function buildWordSetNoRepeat(array $set, $num)
	{
	  $result=array();
	  $this->addLetters($num,$set,array(),$result,array());
	  echo TVarDumper::dump($result,2,true);
	  return $result;
	}
}
?>
[PHP] pobierz, plaintext 

[PiXel2.0]

Mialem troche czasu i napisalem taka funkcje (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

[PHP] pobierz, plaintext 
<?php
function permutacje($lancuch_wejsciowy){
		if(!is_string($lancuch_wejsciowy) or !strlen($lancuch_wejsciowy))
			return false;
		$a = str_split($lancuch_wejsciowy);
		sort($a);
		$lancuch = implode('', $a);
		$znaki = range(strlen($lancuch) - 1, 0);
		$wyniki = array();
		do{
			for($wynik = '', $i = count($znaki) - 1; $i >= 0; $i--)
				$wynik .= $lancuch{$znaki[$i]};
			if(!in_array($wynik, $wyniki))
				$wyniki[] = $wynik;
			$znaki_poprzednie = $znaki;
			for($i = 1; $i < count($znaki); $i++){
				for($znak_nr = $znaki[$i] + 1; $znak_nr < count($znaki); $znak_nr++){
					if(array_search($znak_nr, $znaki) > $i)
						continue;
					$znaki[$i] = $znak_nr;
					for($i2 = $i - 1; $i2 >= 0; $i2--){
						for($i3 = 0; $i3 < count($znaki); $i3++)
							if(!$pozycje = array_keys($znaki, $i3) or max($pozycje) <= $i2)
								break;
						$znaki[$i2] = $i3;
					}
					break 2;
				}
			}
		}while($znaki != $znaki_poprzednie);
		return $wyniki;
	}
?>
[PHP] pobierz, plaintext 

Jako argument podstawiasz lancuch i na wyjsciu masz tablice ze wszystkimi kombinacjami w kolejnosci alfabetycznej.
Dziala tak jak chciales dla ABC, ABA (...) i dla ABCBCCDJAJZZ tez (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)

PS:
Wydaje mi sie, ze taki problem wykracza poza te ktore powinny sie znajdowac w dziale Przedszkole i temat powinien trafic do dzialu o PHP.

Ten post edytował PiXel2.0 15.05.2008, 19:18:37