permutation

gistfile1.cs

	
		public static void permutation()
		{
			string sourceText = "1bc23a";

			// remove duplicates and sort
			string[] s = sourceText.Select(c => c.ToString()).Distinct().OrderBy(c => c).ToArray();

			int combinations = Factorial(s.Length);
			int len = s.Length;

			Console.WriteLine("permutation of "+sourceText+" (total "+combinations+" combinations of "+len+" unique elements)");

			for (int i=0; i<combinations; i++) {

				// generate list of indexes for one row. For example: 0,1,2,3,4,5,6
				List<int> remains = new List<int> ();
				for (int j=0; j<len; j++) {
					remains.Add (j);
				}

				for (int j=0; j<len; j++) {
					int index = (i / Factorial (len - j - 1)) % (len - j);
					index = remains [index];
					remains.Remove (index);
					Console.Write(s[index]+" ");
				}
				Console.WriteLine();
			}
		}

		static int Factorial(int i)
		{
			if (i <= 1)
				return 1;
			return i * Factorial(i - 1);
		}
	
	
/*

Основная хитрость алгоритма в том, что у меня с помощью этой строки:

int index = (i / Factorial (len - j - 1)) % (len - j);

получилось сформировать массив перестоновок такого вида:

		0 0 0 0		
		0 0 1 0     
		0 1 0 0   
		0 1 1 0 
		0 2 0 0 
		0 2 1 0 
		1 0 0 0 
		1 0 1 0 
		1 1 0 0 
		1 1 1 0 
		1 2 0 0 
		1 2 1 0 
		2 0 0 0 
		2 0 1 0 
		2 1 0 0 
		2 1 1 0 
		2 2 0 0 
		2 2 1 0 
		3 0 0 0 
		3 0 1 0 
		3 1 0 0 
		3 1 1 0 
		3 2 0 0 
		3 2 1 0 

причем тут нет ограницений на размер входных данных, работает и с 0 символов и с 10
все, за исключением функции Factorial не рекурсивное

*/