Pętla przez różne zestawy unikalnych permutacji

Question

Mam trudności z rozpoczęciem pracy z kodem układu dla tego problemu.

Mam stałą liczbę liczb losowych, w tym przypadku 8 liczb. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Zostaną one umieszczone w 3 zestawach liczb, z jedynym ograniczeniem, że każdy zestaw zawiera minimum jedną wartość, a każda wartość może być użyta tylko jeden raz. Uwaga: Wszystkie 8 powinny służyć

Na przykład

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

Potrzebuję pętli przez wszystkie możliwe kombinacje zestawu R1, R2, R3. Aby nie jest ważna, to, jeżeli powyższy przykład się, że nie ma potrzeby

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

Co to jest dobra metoda?

Answer 1

Prawdopodobnie nie jest to najlepsze podejście, ale powinno działać.

Określić liczbę kombinacji trzech liczb, które sumują się do 8:

1,1,6 
1,2,5 
1,3,4 
2,2,4 
2,3,3 

aby znaleźć powyżej Zacząłem:

6,1,1 then subtracted 1 from six and added it to the next column... 
5,2,1 then subtracted 1 from second column and added to next column... 
5,1,2 then started again at first column... 
4,2,2 carry again from second to third 
4,1,3 again from first... 
3,2,3 second -> third 
3,1,4 

wiedząc, że mniej niż połowa 2 wszystkie kombinacje muszą być znaleźć ... ale ponieważ lista nie jest długa, równie dobrze możemy iść do końca.

Teraz sortuj każdą listę z 3 od największej do najmniejszej (lub odwrotnie). Teraz sortuj każdą listę 3 względem siebie. Skopiuj każdą unikatową listę do listy unikatowych list. Mamy teraz wszystkie kombinacje, które dodajemy do 8 (pięć list, jak myślę).

Rozważmy teraz listę w powyższym zestawie

6,1,1 wszystkich możliwych kombinacji można znaleźć przez:

8 pick 6, (ponieważ wybraliśmy sześć jest tylko 2 w lewo, aby wybrać z) 2 wybierz 1, 1 wybierz 1 , który działa na 28 * 2 * 1 = 56, warto wiedzieć, ile jest możliwości, abyś mógł przetestować.

wybrać n r (odbiór elementów r z N wszystkich możliwości)

nC = N, R!/[(n-r)! R!]

Więc teraz masz całkowitą liczbę iteracji dla każdego elementu listy dla pierwszej jest to 28 ...

Dobrze zbierając 6 pozycji z 8 jest taki sam, jak tworzenie listy 8 minus 2 elementy, ale które dwa elementy?

Dobrze, jeśli usuniemy 1,2, który pozostawi nam 3,4,5,6,7,8. Przyjrzyjmy się wszystkim grupom 2 ... Zaczynając od 1,2 następna będzie 1,3 ... więc następująca kolumna zostanie odczytana kolumna.

12 
13 23 
14 24 34 
15 25 35 45 
16 26 36 46 56 
17 27 37 47 57 67 
18 28 38 48 58 68 78 

Podsumowując każdej z powyższych kolumnach daje nam 28. (tak to tylko pokryte pierwszą cyfrę na liście (6,1,1) Powtórzyć procedurę dla drugiej cyfry (o jeden), która jest „2 Wybierz 1 "Więc z lewej ponad dwie cyfry z powyższej listy wybieramy jedną z dwóch, a na koniec wybieramy ostatnią:

Wiem, że to nie jest szczegółowy algorytm, ale mam nadzieję, że będziesz w stanie na początek:

Answer 2

Generowanie wszystkich kombinacji podzbiorów rekursywnie w sposób klasyczny Po osiągnięciu punktu, w którym liczba pozostałych elementów jest równa liczbie pustych podzbiorów, ogranicz się tylko do pustych podzbiorów.

Oto implementacja Pythona:

def combinations(source, n): 
    def combinations_helper(source, subsets, p=0, nonempty=0): 
    if p == len(source): 
     yield subsets[:] 
    elif len(source) - p == len(subsets) - nonempty: 
     empty = [subset for subset in subsets if not subset] 
     for subset in empty: 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+1): 
      yield combination 
     subset.pop() 
    else: 
     for subset in subsets: 
     newfilled = not subset 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled): 
      yield combination 
     subset.pop() 

    assert len(source) >= n, "Not enough items" 
    subsets = [[] for _ in xrange(n)] 
    for combination in combinations_helper(source, subsets): 
    yield combination 

a test:

>>> for combination in combinations(range(1, 5), 2): 
... print ', '.join(map(str, combination)) 
... 
[1, 2, 3], [4] 
[1, 2, 4], [3] 
[1, 2], [3, 4] 
[1, 3, 4], [2] 
[1, 3], [2, 4] 
[1, 4], [2, 3] 
[1], [2, 3, 4] 
[2, 3, 4], [1] 
[2, 3], [1, 4] 
[2, 4], [1, 3] 
[2], [1, 3, 4] 
[3, 4], [1, 2] 
[3], [1, 2, 4] 
[4], [1, 2, 3] 
>>> len(list(combinations(range(1, 9), 3))) 
5796 

Answer 3

mam przed sobą Knuth Tom 4, zeszyt 3, Generowanie wszystkich kombinacji i partycji, rozdział 7.2 .1.5 Generowanie wszystkich ustawionych partycji (strona 61 w pakiecie).

Najpierw szczegóły algorytm H ciągi ograniczeniami wzrostu w porządku leksykograficznym powodu George Hutchinson. Wygląda to prosto, ale nie zamierzam teraz zagłębiać się w to.

na następnej stronie pod opracowania kody Szary zestaw przegród zastanawia:

Załóżmy jednak, że nie jesteśmy zainteresowani wszystko partycji; możemy chcieć tylko bloków, które mają m. Czy możemy uruchomić to poprzez mniejszą kolekcję ograniczonych ciągów wzrostu, ciągle zmieniając jedną cyfrę na raz?

Następnie podaje szczegóły rozwiązania z powodu Franka Ruskeya.

Proste rozwiązanie (i pewne, że poprawne) polega na kodowaniu algorytmu H filtrowania na partycjach, gdzie m==3 i żadna z partycji nie jest pustym zestawem (zgodnie z określonymi ograniczeniami). Podejrzewam, że algorytm H działa niesamowicie szybko, więc koszt filtrowania nie będzie duży.

Jeśli implementujesz to na 8051, możesz zacząć od algorytmu Ruskey, a następnie filtrować tylko na partycjach zawierających pusty zestaw.

Jeśli wdrażasz to na czymś mniejszym niż 8051 i milisekundach, możesz wysiać każdą z trzech partycji za pomocą unikalnego elementu (prosta pętla zagnieżdżona z trzema poziomami), a następnie powiększyć partycją na pozostałych pięć elementów dla m==3 przy użyciu algorytmu Ruskey. Nie musisz niczego filtrować, ale musisz śledzić, które pięć elementów pozostało do podziału.

Zaletą filtrowania w dół od ogólnego algorytmu jest to, że nie trzeba weryfikować żadnych własnych sprytu, a później zmienisz zdanie o swoich ograniczeniach, bez konieczności zmiany sprytu.

Może nawet rozwiążę problem później, ale to wszystko na teraz.

P.S. dla gupików Javy: odkryłem, że "George Hutchison ograniczył łańcuchy wzrostu" w pewnym pakiecie ca.ubc.cs.kisynski.bell z dokumentacją dla metody growthStrings(), która implementuje algorytm Hutchisona.

Wydaje się być dostępne w http://www.cs.ubc.ca/~kisynski/code/bell/

Answer 4

Turn problemu na jego głowie i znajdziesz prosta rozwiązanie. Masz 8 liczb, z których każda musi być przypisana do dokładnie jednej grupy; "Rozwiązanie" jest rozwiązaniem tylko wtedy, gdy do każdej grupy przypisano co najmniej jeden numer.

trywialne realizacja wiązałaby 8 pętli i kilka jeśli jest (Pseudokod):

for num1 in [1,2,3] 
    for num2 in [1,2,3] 
    for num3 in [1,2,3] 
     ... 
     if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3)) 
      Print Solution! 

To może być również realizowane rekursywnie, używając dwóch tablic i kilka funkcji. Dużo ładniejszy i łatwiejszy do debugowania/follow (pseudokod):

numbers = [1, 2, 3, 4, 5, 6, 7, 8] 
positions = [0, 0, 0, 0, 0, 0, 0, 0] 

function HandleNumber(i) { 
    for position in [1,2,3] { 
    positions[i] = position; 
    if (i == LastPosition) { 
     // Check if valid solution (it's valid if we got numbers in all groups) 
     // and print solution! 
     } 
    else HandleNumber(i+1) 
    }  
} 

Trzeci wdrożenie byłoby wykorzystać żadnej rekurencji i trochę backtracking. Pseudokod, ponownie:

numbers = [1,2,3,4,5,6,7,8] 
groups = [0,0,0,0,0,0,0,0] 

c_pos = 0 // Current position in Numbers array; We're done when we reach -1 
while (cpos != -1) { 
    if (groups[c_pos] == 3) { 
     // Back-track 
     groups[c_pos]=0; 
     c_pos=c_pos-1 
    } 
    else { 
    // Try the next group 
    groups[c_pos] = groups[c_pos] + 1 
    // Advance to next position OR print solution 
    if (c_pos == LastPostion) { 
     // Check for valid solution (all groups are used) and print solution! 
     } 
    else 
     c_pos = c_pos + 1 
    } 
}