C# - Permutáció kalkulálása

forráskód letöltése
Készítünk egy programot, amely segítségével kikalkulálhatjuk a megadott elemek összes ismétléses vagy ismétlés nélküli permutációját. Lekérdezhetjük pusztán az eredményt, de lehetőség van arra is, hogy az összes lehetséges permutáció egy TXT típusú állományba kerüljön, soronként egyetlen kalkulációval és a legvégén a permutációk számával.
n elem egy meghatározott sorrendben való elhelyezését az n elem egy permutációjának nevezzük. Ha az n elem különböző, akkor ismétlés nélküli, ha tartalmaz egyforma elemeket, akkor ismétléses permutációról beszélünk.
Az ismétlés nélküli permutációk száma: n! Az ismétléses permutációk száma n!/(k1!*k2!...kr!), ahol r számú elem ismétlődik.
Az állomány létrehozásához és az állományba történő íráshoz a Stream és a BinaryWriter osztályokat használjuk.
Stream st = File.Open(textBox1.Text, FileMode.Create);
st.Seek(0, SeekOrigin.End);               
BinaryWriter bw = new BinaryWriter(st);
Külön függvényt készítünk az ismétléses és az ismétlés nélküli permutációk kiszámítására. Mindkét függvény rekurzív.
A Calculate függvény
private void Calculate(BinaryWriter bw, StringCollection list, string s, int level)
A bw paraméterben mindig a létrehozott BinaryWriter-t adjuk meg, amely segítségével a következő elem beírható az állományba. Ha egy elemet felhasználtunk, akkor azt már nem tehetjük vissza. A list paraméterben a függvény mindig a még felhasználható elemeket kapja. Ebből az elemlistából már hiányoznak az előző helyeken felhasznált elemek. Az s változó az eddig kikalkulált elemek sorrendjét tartalmazza, vesszővel elválasztva. A level változó a rekurzió szintjét adja meg.
A függvény belsejében a feldolgozást logikailag kétfelé kell bontanunk.
Ha a rekurzió szintje elérte a permutálandó elemek számát, akkor az s változó tartalmát ki kell írnunk az állományba.
if (level == listBox1.Items.Count)
{
  s += list[0];
  bw.Write(s + (char)(13) + (char)(10));
  rows++;
}
Ha nem, akkor rekurzív módon, újra meg kell hívnunk a függvényt.
for (int i = 0; i < list.Count; i++)
{
  if (level == 1)
    s = "";
  l.Clear();
  for (int j = 0; j < list.Count; j++)
    l.Add(list[j]);
  l.RemoveAt(i);
  Calculate(bw, l, s + list[i] + ",", level + 1 );
}
Az l segédváltozó segítségével az új függvénynek olyan elemkészletet adunk, amelyből már hiányzik az aktuálisan felhasznált elem.
A CalculateRep függvény
A függvény működésének lényege ugyanaz, mint a Calculate függvénynek. Itt azonban, amikor egy kalkulációban meghatározzuk a soron következő elemet, törölnünk kell a listából az összes egyforma elemet. Ehhez a removedList segédobjektumot használjuk. Fontos, hogy az eredeti elemkészletünk is mindig megmaradjon. Erre az újabb függvényhívásoknál van szükségünk. Az aktuális elem feldolgozása mindig a removedList objektumból történik.
Mielőtt újabb rekurziót indítanánk, itt is el kell távolítanunk az elemlistából az éppen felhasznált elemet. Itt egy elemből akár több is lehet, de csak egyetlen elemet kell törölnünk.
for (int i = 0; i < removedList.Count; i++)
{
  if (level == 1)
    s = "";
  l.Clear();
  for (j = 0; j < list.Count; j++)
    l.Add(list[j]);
  j = 0;
  while (l[j] != removedList[i])
    j++;
  l.RemoveAt(j);
  CalculateRep(bw, l, s + removedList[i] + ",", level + 1);
}