Kombinacje zbioru rekurencyjnie

0

Witam! mam do napisania projekt na zaliczenie na ostatnim roku studiów. Otóż potrzebuję aby program wypisywał na ekranie wszystkie możliwe kombinacje danego zbioru liter. Szukałem na innych stronach i gdzie tylko się dostałem tematy owszem są ale zawsze błędnie nazwane, bo chodzi o permutacje. Ja potrzebuję stricte kombinacje. Nie mam pojęcia jak się za to zabrać. Za wszystkie sugestie z góry dziękuję.

0

troche slabo jak na ostatnim roku studiow nie dajesz rady z czyms takim :P
poza tym co to za uczelnia ze na ostatnim roku na zaliczenie sa takie projekty?

wzor znasz na ilosc kombinacji i permutacji (jesli nie to wikipedia)

wiec jesli chcesz 4 po 2 kombinacji, to jest ich 6
wystarczy ze ze policzysz wszystkie permutacje (tak permutacje) zbioru 4 elementowego binarnego, czyli 0011 (zalezy jak przyjmiesz, powiedzmy ze jak 1 to ten element biore do kombinacji, oczywiscie 1 jest tylke co k, w tym przykladzie 2)
ABCD
0011 = CD
0101 = BD
1010 = AC
1100 = AB
0110 = BC
1001 = AD

4 po 3
ABCD szukamy premutacji 1110
1110 = ABC
1101 = ABD
1011 = ACD
0111 = BCD

0

massther dosyć to skomplikowane biorąc pod uwagę cały alfabet czyli około 24 znaki.
ale pomyślę dziękuję za naprowadzenie, zobaczę co da się zrobić :)

0

Jest taki fajny algorytm do generowania losowych liczb z totolotka. W skrócie wygląda to tak:

  1. Generujemy tablicę n elementów i wypełniamy ją kolejnymi liczbami.
  2. Losujemy jeden element i wrzucamy go na wyjście, do innej tablicy, czy jak komu pasuje.
  3. Ostatni element tablicy wrzucamy w miejsce wylosowanego elementu.
  4. Zmniejszamy rozmiar tablicy o jeden.
  5. Jeśli wylosowaliśmy już tyle liczb ile trzeba kończymy algorytm, w przeciwnym wypadku wracamy do punku 2.

W podobny sposób możesz rozwiązać swój problem.

0
grayter napisał(a)

massther dosyć to skomplikowane biorąc pod uwagę cały alfabet czyli około 24 znaki.

ale co jest skomplikowane?
tak czy siak musisz wygenerowac 24 po k czyli 24!/k!(24-k)!
czyli w najgorszym przypadku 2 704 156 elementow (k=12)
co jest wg ciebie nie tak? zlozonosc obliczeniowa czy pamiec?
jesli powiedzialbys to 5-10 lat temu nie zdziwilbym sie, ale dla kompa z ramem 2-4GB i 2x2GHz jaki to klopot?
jakies pomocnicze struktury w pamieci nie powinny przekroczyc 300MB - 600MB :)
wyjscie ewentualnie mozesz od razu do pliku zrzucac

0
class Program
    {
        class Combinatorics<T>
        {
            public IEnumerable<List<T>> Permutations(List<T> list)
            {
                if (list.Count == 0)
                    yield return new List<T>();
                else
                {
                    T element = list.ElementAt(0);
                    List<T> listCopy = new List<T>(list);
                    listCopy.RemoveAt(0);
                    foreach (List<T> subList in Permutations(listCopy))
                    {
                        for (int i = 0; i <= subList.Count; i++)
                        {
                            List<T> subListCopy = new List<T>(subList);
                            subListCopy.Insert(i, element);
                            yield return subListCopy;
                        }
                    }
                }
            }

            public IEnumerable<List<T>> Combinations(List<T> list)
            {
                if (list.Count == 0)
                    yield return new List<T>();
                else
                {
                    T element = list.ElementAt(0);
                    List<T> listCopy = new List<T>(list);
                    listCopy.RemoveAt(0);
                    foreach (List<T> subList in Combinations(listCopy))
                    {
                        List<T> subListCopy = new List<T>(subList);
                        yield return subListCopy;
                        subListCopy.Insert(0, element);
                        yield return subListCopy;
                    }
                }
            }

            public IEnumerable<List<T>> Variations(List<T> list)
            {
                foreach (List<T> subList in Combinations(list))
                    foreach (List<T> subList2 in Permutations(subList))
                        yield return subList2;
            }

            public void Print(List<T> list)
            {
                foreach (T el in list)
                    Console.Write(el + " ");
                Console.WriteLine("");
            }
        }

        static void Main(string[] args)
        {
            Combinatorics<int> c = new Combinatorics<int>();
            List<int> l = new List<int>();
            l.Add(1);
            l.Add(2);
            l.Add(3);

            foreach (List<int> l2 in c.Combinations(l))
                c.Print(l2);

            Console.ReadKey();
        }
    }
0

Uzyta pamiec to O(k^2) gdzie k to rozmiar zbioru elementow z ktorych chcemy kombinacje

0

http://www.ideone.com/Cn0gx

Scala niby lata na .NECie, ale nie wiem w jakim "stopniu".

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0