Getting wszystkie możliwe kombinacje z listy numerów

Question

szukam skuteczny sposób, aby osiągnąć ten cel:

• masz listę numerów 1 ..... n (typowo: 1 .. 5 lub 1..7 lub mniej - rozsądnie małe, ale mogą się różnić w różnych przypadkach)

• potrzebne są wszystkie kombinacje wszystkich długości dla tych liczb, np. wszystkie kombinacje tylko jednej liczby ({1}, {2}, .... {n}), a następnie wszystkie kombinacje dwóch różnych liczb ({1,2}, {1,3}, {1,4}. .... {n-1, n}), wszystkie kombinacje fo trzy z tych numerów ({1,2,3}, {1,2,4}) i tak dalej

Zasadniczo w obrębie grupy kolejność nie ma znaczenia, więc {1,2,3} jest równoważne {1,3,2} - to tylko kwestia uzyskania wszystkich grup liczb x z tej listy

Wygląda na to, że powinno być prostym algorytmem do tego - ale do tej pory szukałem na próżno. Większość algorytmów kombinatorycznych i permutacyjnych wydaje się: a) brać pod uwagę porządek (np. 123 nie jest równe 132) i zawsze wydaje się działać na pojedynczym ciągu znaków lub liczb ...

Każdy ma świetny, fajny algorytm w rękawie?

Dzięki!

Answer 1

Po prostu zwiększ liczbę binarną i weź elementy odpowiadające ustawionym bitom.

Na przykład 00101101 oznaczałoby podjęcie elementy na indeksach 0, 2, 3 i 5. Ponieważ lista jest po prostu 1..n element jest po prostu indeks + 1.

To wygeneruje permuatacje w porządku. Innymi słowy, wygenerowany zostanie tylko {1, 2, 3}. Nie {1, 3, 2} lub {2, 1, 3} lub {2, 3, 1}, itp.

Answer 2

To jest coś, co napisałem w przeszłości, aby wykonać takie zadanie.

List<T[]> CreateSubsets<T>(T[] originalArray) 
{ 
    List<T[]> subsets = new List<T[]>(); 

    for (int i = 0; i < originalArray.Length; i++) 
    { 
     int subsetCount = subsets.Count; 
     subsets.Add(new T[] { originalArray[i] }); 

     for (int j = 0; j < subsetCount; j++) 
     { 
      T[] newSubset = new T[subsets[j].Length + 1]; 
      subsets[j].CopyTo(newSubset, 0); 
      newSubset[newSubset.Length - 1] = originalArray[i]; 
      subsets.Add(newSubset); 
     } 
    } 

    return subsets; 
} 

To uniwersalne, a więc będzie pracować za wskazówki, tęskni, smyczki, Foo itp

Answer 3

Nie mój kod, ale szukasz na PowerSet. Google dał mi to rozwiązanie, które wydaje t praca:

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) 
{ 
    return from m in Enumerable.Range(0, 1 << list.Count) 
       select 
        from i in Enumerable.Range(0, list.Count) 
        where (m & (1 << i)) != 0 
        select list[i]; 
} 

Źródło: http://rosettacode.org/wiki/Power_set#C.23