Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: zacma permutacyjna
Forum PHP.pl > Inne > Hydepark
nospor
17.02.2014, 15:36:50
Hej, mam zacme matematyczną i albo nie moge sobie przypomniec, albo mi sie wydaje ze to cos ma nazwe wink.gif

Jak sie nazywa takie cos, co z liczb 1 2 3 da mi ciagi:
1 2 3
1 2
1 3
2 3

A z liczb 1 2 3 4
1 2 3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2
1 3
1 4
2 3
2 4
3 4


itd itd
Ma to jakąs nazwe?
Kshyhoo
17.02.2014, 15:50:16
Permutacja jest szczególnym przypadkiem wariacji bez powtórzeń? To?
com
17.02.2014, 16:40:09
Podciąg wink.gif

http://pl.wikipedia.org/wiki/Podci%C4%85g_(matematyka)

ale jako moderator to z nazwa tematu to się nie postarałeś tongue.gif
rzymek01
17.02.2014, 16:45:14
ludzie... to są kombinacje...

dla pragnących poszerzyć swoją wiedzę: https://en.wikipedia.org/wiki/Combination
nospor
17.02.2014, 16:59:57
Cytat
ale jako moderator to z nazwa tematu to się nie postarałeś
Jako ze jest to Hydepark, wydaje mi sie ze temat jest w miare ok. No ale nie jestem obiektywny wink.gif

Moze i faktycznie to kombinacje. Mniejsza o wiekszosc.
Bardziej interesuje mnie kod php, ktory wykona to co pokazalem. Jest w stanie ktos z tym pomoc? Wiem, to jest proste, ale mam dzisiaj taką zacme, ze siedze, patze, mysle i guzik :/

Crozin
17.02.2014, 17:04:22
http://stackoverflow.com/questions/127704/...elements-from-n
com
17.02.2014, 17:10:25
nospor niech będzie biggrin.gif widzę faktycznie gorszy dzień http://r.je/php-find-every-combination.html wink.gif
nospor
17.02.2014, 18:19:03
@com poprosilbym w kolejnosci i w zbiorze wynikow dokladnie takim, jaki podalem wink.gif
@Crozin jest tam wiele ciekawych rzeczy, ale wiekszosc w c,z ktorym juz dawno nie mialem do czynienia, a przez co nie rozumiem idei.
Dorwalem jeden js stamtad, ktory chyba robi to co chce, ale kurka po przerobieniu tego na php juz nie robi tego co chce wink.gif

js:
Kod
function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    
    if (k > set.length || k <= 0) {
        return [];
    }
    
    if (k == set.length) {
        return [set];
    }
    
    if (k == 1) {
        combs = [];
        for (i = 0; i < set.length; i++) {
            combs.push([set[i]]);
        }
        return combs;
    }
    
    // Assert {1 < k < set.length}
    
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        head = set.slice(i, i+1);
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}


Ferelna przerobka na php
[PHP] pobierz, plaintext 
  1. $t = array(1,2,3,4);
  2. function k_combinations($set, $k) {
  3. 	//$ i, j, combs, head, tailcombs;
  4.  
  5. 	if ($k > count($set) || $k <= 0) {
  6. 		return array();
  7. 	}
  8.  
  9. 	if ($k == count($set)) {
  10. 		return $set;//[set];
  11. 	}
  12.  
  13. 	if ($k == 1) {
  14. 		$combs = array();
  15. 		for ($i = 0; $i < count($set); $i++) {
  16. 			$combs[]=$set[$i];
  17. 		}
  18. 		return $combs;
  19. 	}
  20.  
  21. 	// Assert {1 < k < set.length}
  22.  
  23. 	$combs = array();
  24. 	for ($i = 0; $i < count($set) - $k + 1; $i++) {
  25. 		$head =  array_slice($set, $i,1);//set.slice(i, i+1);
  26. 		$tailcombs = k_combinations(array_slice($set, $i+1), $k - 1);
  27. 		for ($j = 0; $j < count($tailcombs); $j++) {
  28. 			$tmp = $head;
  29. 			$tmp[]=$tailcombs[$j];
  30. 			$combs[]=$tmp;
  31. 		}
  32. 	}
  33. 	return $combs;
  34. }
  35.  
  36. $tt = k_combinations($t,3);
  37. print_r($tt);
  38.  
[PHP] pobierz, plaintext


Albo w c, ten kod, robi to co chce:
Kod
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Tylko z C juz nie mialem bardzo dawno do czynienia i nie potrafie przetlumaczyc :/

edit:
Dobra, mam. Post crozina nakierowal mnie na wlasciwą szukajkę smile.gif
com
17.02.2014, 19:19:02
jakby ktoś jeszcze potrzebował http://ideone.com/Mn2niT wink.gif

a Ten js to akurat nie spełniał tego co potrzebowałeś tongue.gif
nospor
18.02.2014, 08:43:27
Cytat
a Ten js to akurat nie spełniał tego co potrzebowałeś
Spelnial. Testowalem i dzialal jak chcialem tongue.gif
Pawel_W
19.02.2014, 08:25:43
prosta rekurencja, bierzesz albo nie bierzesz element smile.gif coś takiego powinno zadziałać:

[PHP] pobierz, plaintext 
  1. $arr = array(1,2,3,4,5);
  2. $n = 5;
  3. $k = 3;
  4.  
  5. function gen($arr, $n, $k, $result, $i){
  6.     if($i == $n){
  7.         //$result bedzie zawierala wygenerowany podciag
  8.     } else if($n-$k >= count($result) + $i) { // warunek na to zeby nie leciec dalej z rekurencja jezeli juz nie mamy szans wybrac k elementow
  9.         gen($arr, $n, $k, $result, $i+1); // nie bierzemy elementu $arr[$i]
  10.         $result[] = $arr[$i];
  11.         gen($arr, $n, $k, $result, $i+1); // bierzemy element $arr[$i]
  12.     }
  13. }
  14.  
  15. gen($arr, $n, $k, array(), 0);
[PHP] pobierz, plaintext
nospor
19.02.2014, 08:37:28
@Pawel to mialby byc gotowy kod, czy tylko pseudo pisany z palca bez jakiegokolwiek sprawdzania? wink.gif
Pawel_W
19.02.2014, 17:02:27
pseudo pisany z palca, jednak poza warunkiem, który podałem zły (powinien być 
[PHP] pobierz, plaintext 
  1. count($result) == $k
[PHP] pobierz, plaintext
i drugi 
[PHP] pobierz, plaintext 
  1. $n-$i >= $k - count($result)
[PHP] pobierz, plaintext
wszystko się zgadza, także nie widzę problemu
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.