Kombinacje zbioru rekurencyjnie

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ę.

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

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ć :)

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.

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

http://www.codeproject.com/KB/recipes/Combinatorics.aspx

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();
		}
	}

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

http://www.ideone.com/Cn0gx

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