Základy kombinatoriky v C#...

readme.md

Permutace

Permutace (variace bez opakování, kde n=k) jsou všechna různá pořadí z množiny prvků (například prohazování otázek u testu je permutováním těchto otázek, protože je požadováno, aby všichni měli stejné otázky a stejný počet).

Vzorec

k = ((m-1)/(n-1)!)+1
l = ((m-1)%(n-1)!)+1

Kde k je cifra na právě zkoumané pozici a l je kolikátou pozici budeme chtít příště. Čili v rekurzi vypíši k, m položím rovno l a n zmenším o jedna. Také je třeba udržovat množinu ještě nepoužitých prvků (obvykle čísel).

Podrobnější popis a kód v Haskellu:

• "Matematické Fórum":http://forum.matweb.cz/viewtopic.php?pid=78733

Variace s opakováním

Variace s opakovaním jsou všechna možná uspořádání prvků z dané množiny a záleží na pořadí.

kombinatorika.cs

using System;

namespace kombinatorika
{
  class MainClass
	{
		public static void Main (string[] args)
		{
			Console.Write ("Hello World!\nPočet hodnot (jazyk): ");
			int n = 4;//int.Parse( Console.ReadLine() );
			Console.Write ("\nPočet míst (vstupů): ");
			int m = 2;//int.Parse( Console.ReadLine() );
			
			PrintArray( VariaceSOpakovani( 3,2) );
		}
		
		public static void Permutace() {
			int[] perm = {1,2};
			Console.WriteLine( "1,2>" + findPerOrderNum(perm));
			
			perm[0]=2;
			perm[1]=1;
			Console.WriteLine( "2,1>" + findPerOrderNum(perm));

			while(true)
			{
				Console.Write("Permutaci kolika čísel (n): "); 
				int n = Reader.Console().Int(); 
				if(n < 0) break;
				Console.Write("Kterou permutaci chcete (m): "); 
				int m = Reader.Console().Int();		
				Console.WriteLine( "m-ta permutace: {0}");
				int i = Permutace( m, n );
				Console.WriteLine( i );
				Console.WriteLine( "For quit write: n < 0." );
			}
		}
		
		public static int[,] VariaceSOpakovani(int n, int m) {
			if( m > n ) Console.WriteLine("Míst je více, než možných hodnot. Nelze je tedy obsadit všechny.");
			
			int[,] pole = new int[ m , (int) Math.Pow( n , m ) ];

			Console.WriteLine("\nPole velikosti: [{0},{1}]", pole.GetLength( 0 ), pole.GetLength( 1 ) );
			
			int i, j, val, opakuj;
			
			for( i=m-1 ; i >= 0 ; i-- ) {
				val = 0;
				opakuj = (int) Math.Pow( n, m - i -1);
				for( j = 0; j < pole.GetLength(1) ; j++ ) {
					pole[i,j] = val;
					opakuj--;
					if( opakuj <= 0 ) {
						val++;
						opakuj = (int) Math.Pow( n, m - i -1);	// podle toho v jakem jsem sloupci
					}
					if( val == n ) val = 0;
				}
			}
			return pole;
		}
		
		public static void PrintArray( int[,] pole ) {
			for(int j=0 ; j < pole.GetLength(1) ; j++) {
				for(int i=0;i< pole.GetLength(0);i++) {
					Console.Write("{0} ", pole[i,j]);	
				}
				Console.WriteLine();
			}	
		}
	
		public static int Permutace(int m, int n) // m-ta permutace cisel 1,...,n
		{
			
			#region /* Initialization array of don't used and array for answer */
			int[] toUse = new int[n];
			for(int i = 0; i<n; i++)
				{ toUse[i]=i+1; }		
			
			int[] answer = new int[n]; 		
			#endregion
			
			permWorker(m, n, toUse, answer, 0);
			
			return (int) arrayToInt(answer);
		}
		
		private static void permWorker(int m, int n, int[] toUse, int[] answer, int i)
		{	
			if(n==1) {answer[i] = toUse[i]; return; } 
			
			int k = ( ( (m-1) / factorial(n-1) ) +1 );
			
			answer[i] = toUse[i+k-1];	// corect answer
			toUse[i+k-1] = 0;			// was used
			
			int l = ( ( (m-1) % factorial(n-1) ) +1 );
			
			i++;
			Array.Sort(toUse);
			
			permWorker(l, n-1, toUse, answer,i);
		}

	#region //TOFIX
		protected static int findPerOrderNum(int[] permutace)
		{
			return findPerOrderNum(permutace, 0, -1);
		}
		
		protected static int findPerOrderNum(int[] permutace, int done, int previous)
		{
			int i;
			if(done == permutace.Length -1) return 0;
			
			if(done >= 0) 
			{
				for(i = done; i < permutace.Length; i++) 
				{
					if(permutace[i] > previous) permutace[i]++;
				}
			}
			return (permutace[done +1] -1) *factorial(permutace.Length - done -1) + 
				findPerOrderNum(permutace, done +1, permutace[done+1]);
		}
	#endregion	
		
		public static int factorial(int n) 
		{
			if(n >= 2) return n * factorial(n-1);
			else return 1; 			// 1! == 1, 0! == 1
		}
		
		private static int arrayToInt(int[] pole) /* Help procedure */
		{
			int i = 0;
			int k = 1;
			for(int j=0; j <= (pole.Length -1) ; j++)
			{
				i += pole[pole.Length-1-j] * k;
				k *= 10;
			}
			return i;
		}
		
		private static bool IsPerm(int[] perm) 
		{
			Array.Sort<int>(perm);
			for(int i = 0; i <= perm.Length - 2; i++)
				{
					if(perm[i] == perm[i+1]) return false; 
				}
			return true;
		}
  }
}