[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ę
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

[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

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

[Aztech]

Dwa słowa komentarza do Twojego kodu
Zaznaczyłem pomógł, bo faktycznie kod działa, tak jak napisałem w założeniach w pierwszym poście, ale jest ale Rozjeżdża się całkowicie w przypadku kiedy w stringu są polskie litery - zwraca nieprawidłową ilość permutacji - trzeba używać funkcji mb_* . Ale z racji, że bez polskich literek działa, to zaznaczyłem iż pomogłeś - napracowałeś się i Ci się należy.

Mi również udało się spłodzić metodę (kombinując to co znalazłem w sieci wraz z tym co napisałem)
Zwracam sobie tablicę 2-wymiarową, gdzie pierwszy wymiar, to liczba liter. Funkcja ma dodatkowe opcje: zwracaj tylko permutacje o zadanej długości (od..do) spośród ciągu.

[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;
	}
 
	public function buildCombinations($length, $fromSublength, $toSublength, array $letters) 
	{ 
	  $out_scheme = array(); 
 
	  if ($sublength>$length) $toSublength = $length;
 
	  $max = $this->factorial($length);
   
	  for ($a=0; $a<($length); $a++) 
		$options[$a]=$pattern[$a]=$a;
 
	  for ($x=0; $x<$max; $x++) 
	  { 
		$N=$x; 
		for ($i=1; $i<= $length;) 
		{ 
		  $pattern[($length-$i)]=$N%$i; 
		  $N=$N/$i; 
		  $i++; 
	  }
	  unset($perm);
	  $b=$options;
	  foreach($pattern AS $offset) 
	  { 
		list($char)=array_splice($b,$offset,1);
		$perm[]=$char; 
		}
		for($l=$fromSublength;$l<=$toSublength;$l++)
		{
		  $m=array_slice($perm,0,$l);
		  $out_scheme[$l][]=implode('-',$m);
		}
	  }
	  for($l=$fromSublength;$l<=$toSublength;$l++)
	  {
		$out_scheme[$l]=array_unique($out_scheme[$l]);
		foreach ($out_scheme[$l] as $scheme)
		{
		  $scheme=str_replace(array_keys($letters),$letters,$scheme);
		  $return[$l][] = implode('',explode('-',$scheme));
		}
	  }
 
	  return $return;
 
	}
?>
[PHP] pobierz, plaintext 

Ten post edytował Aztech 15.05.2008, 23:10:39

[Cysiaczek]

Przenoszę na PHP