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