wszystkie mozliwe kombinacje, algorytm Opcje

[deniol13]

witam, poszukuje skryptu/algorytmu ktory z jakiejs tablicy ktora zawiera integery wszystkie kombinacje bez powtorzen
np

$tab[a] = 1;
$tab[b] = 2;
$tab[c] = 3;

wszystkie kombinacje to
123
213
321
312
231
i moze jeszcze pare

[cojack]

http://pl.wikipedia.org/wiki/Kombinacja_be...%C3%B3rze%C5%84

n/c

@edit
a nawet http://pl.wikipedia.org/wiki/Wariacja_bez_...%C3%B3rze%C5%84

Ten post edytował cojack 5.07.2010, 00:25:09

[paxton]

10 sekund szukania w google

[PHP] pobierz, plaintext 
<?php
    header('Content-Type: text/plain');
 
    function showCombinations($string, $traits, $i)
    {
        if ($i >= count($traits))
            echo trim($string) . "\n";
        else
        {
            foreach ($traits[$i] as $trait)
                showCombinations("$string $trait", $traits, $i + 1);
        }
    }
 
    $traits = array
    (
        array(1, 2, 3, 4),
        array(1, 2, 3, 4),
		array(1, 2, 3, 4)
    );
 
    showCombinations('', $traits, 0);
?>
[PHP] pobierz, plaintext 

[set4812]

http://forum.php.pl/index.php?showtopic=15...mp;#entry755035

[thek]

Set... Mój post jaki linkujesz tyczy wariacji z powtórzeniami. Nie kombinacji z powtórzeniami. A patrząc co chce autor to ma to być wariacja, ale bez powtórzeń (ważna kolejność, nie może się powtarzać element). Jak najprościej zrobić ją? Algorytm:
1. Weź tablicę liczb i usuń duplikaty ( no chyba, że może być kilka wystąpień tej samej liczby, ale wątpię, bo to spowoduje wystąpienie duplikatów w wyniku! )
2. W pętli przesuwaj się po wszystkich elementach tablicy
3. Zastosuj (ilość_elementów-2) takich pętli pomniejszonych o element pętli wyższego rzędu. Jak to miałoby wyglądać?
tablica = (2,4,7,9)
Pętla_1 (2,4,7,9)
Bierzesz 2, Pętla_2 (4,7,9)
Bierzesz 4, Pętla_3 (7,9)
Z tego dostaniesz liczby 2,4,7,9 i 2,4,9,7
Zmienia się Pętla_2, która wskazuje teraz nie na 4, ale 7. Pętla_3 też się zmienia! Zawiera bowiem (4,9)
Mamy więc 2,7,4,9 i 2,7,9,4
Znowu zmiana w Petla_2 z 7 na 9 i po raz kolejny Pętla_3 zmiany uwidacznia (4,7)
Mamy 2,9,4,7 i 2,9,7,4
Zarówno Pętla 2 i 3 doszły do ostatnich elementów, więc zmiana w Pętla_1, z 2 na 4. Lec tak dalej a sam zauważysz jak to ma działać Podpowiem... znów zagnieżdżone rekurencyjnie foreach

[cojack]

Co Wy nawet do wzoru nie potraficie podstawić liczb?

[PHP] pobierz, plaintext 
 
function silnia( $x) {
  if( $x == 0 )
    return 1;
  return $x * silnia( $x - 1 );
};
 
$n = 3; // czyli mamy 1,2 i 3
$k = 3; // kombinacja 3 cyfr
 
$wynik = ( (silnia( $n ) / silnia( $n - $k ) );
[PHP] pobierz, plaintext 

takie trudne?

[Crozin]

Co Wy nawet do wzoru nie potraficie podstawić liczb?

Eee.. a wiesz jaka jest różnica pomiędzy obliczeniem ilości tych wariacji, a wygenerowaniem ich?

[cojack]

Nie ma.


@EDIT a jednak jest ;D

Ten post edytował cojack 6.07.2010, 08:03:09

[celbarowicz]

człowieku, to nie są kombinacje, to są permutacje.

[thek]

To ja po kilku postach naszkicuję szybko algorytm:
1. Weź tablicę i usuń duplikaty.
2. Jeśli tablica ma jakieś elementy weź ją i ustaw ją do przechodzenia w pętli
3. Jeśli tablica ma 1 element wyświetl elementy ze znajdujących się "wyżej" pętli i ten element oraz wróć do pętli wyższego rzędu i przesuń licznik na kolejny element
3. Jeśli ma więcej elementów, tablicę pomniejsz o wybrany element
4. Pomniejszona tablica jest pętlą kolejnego rzędu, czyli wracamy do kroku 2.

Można to optymalizować jak ja zasugerowałem, czyli gdy tablica ma już tylko 2 elementy, to wyświetlamy wszystkie wcześniejsze a owe dwa elementy tylko zamieniamy miejscami w wynikach. Z jednej rekurencji wtedy spadamy dodając 2 wyniki w tym przebiegu.

[celbarowicz]

szkic niezbyt ambitnego sposobu wypisywania wszystkich permutacji zbioru np:{a,b,c,d,e,...}

w tablicy t1 umieszczamy w t1[1] element a , t1[1]=a
pobieramy następny element ->b , i w nowej tablicy t2 wpisujemy w t2[1] łańcuch ba czyli: t2[1] = ba
a w t2[2] łańcuch ab czyli: t2[2] = ab
---------------------------------------------------------------------------------------------------------------------------------
teraz manewry łańcuchem na elemencie t2[1] = ba pobieramy element c w wpisujemy do tablicy t1

t1[1]=cba
t1[2]=bca
t1[3]=bac
podobnie robimy to z t2[2] = ab t1[4]=cab
t1[5]=acb
t1[6]=abc
--------------------------------------------------------------------------------------------------------------------
wykorzystując poprzednie dane z tablicy t1 i pobierając następny element d mamy:
(teraz dane wprowadzamy ponownie do tablicy t2)
t1[1]=cba daje nam t2[1]=dcba
t2[2]=cdba
t2[3]=cbda
t2[4]=cbad
--------------------------------------------------------------------------------------------------------
t1[2]=bca daje nam t2[5]=dbca
t2[6]=bdca
t2[7]=bcda
t2[8]=bcad
--------------------------------------------------------------------------------------------------------
itd dla t1[3] ,...,t1[6]

=================================================================
przy pobraniu następnego elementu ->e dane będą wpisywane do tablicy t1 a wydłużane będą łańcuchy tablicy t2

pozdrawiam.

[Fifi209]

Masz tutaj dwie metody:

[PHP] pobierz, plaintext 
<?php
 
	function silnia($x) {
		if ($x == 0) {
			return 1;
		}elseif ($x > 0) {
			for ($i=1,$y=1; $i <= $x; $i++) {
				$y *= $i;
			}
			return $y;
		}else{
			return 0;
		}
	}
 
	function permutation($array) {
		$x = array();
		$l = silnia(count($array));
 
		while (count($x) != $l) {
			$temp = implode('', $array);
			$temp = str_shuffle($temp);
			if (!in_array($temp, $x)) {
				$x[] = $temp;
			}
		}
 
		return $x;
	}
 
	function permutation_r($array) {
		static $temp = array();
		if (count($temp) != silnia(count($array))) {
			$x = implode('', $array);
			$x = str_shuffle($x);
			if (!in_array($x,$temp)) {
				$temp[] = $x;
			}
			unset($x);
			return permutation_r($array);
		}else{
			return $temp;
		}
	}
 
	echo '<pre>';
		$t = permutation(array('a','b','c','d','e','f'));
		print_r($t);
 
?>
 
[PHP] pobierz, plaintext 

Jednak z góry piszę, że nie są one optymalne.
permutation będzie działało najprawdopodobniej szybciej od permutation_r - albo przynajmniej mniej pamięci zje.

Ten post edytował fifi209 7.07.2010, 21:03:53