Generating permutations and combinations

Question

How can this code be improved?

using System;
//using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace Combinatorics
{
public class Permutation
{
 private int[] data = null;
 private int order = 0;
 public Permutation(int n)
 {
 this.data = new int[n];
 for (int i = 0; i < n; ++i)
 {
 this.data[i] = i;
 }
 this.order = n;
 }
 public Permutation(int n, int k)
 {
 this.data = new int[n];
 this.order = this.data.Length;
 // Step #1 - Find factoradic of k
 int[] factoradic = new int[n];
 for (int j = 1; j <= n; ++j)
 {
 factoradic[n - j] = k % j;
 k /= j;
 }
 // Step #2 - Convert factoradic to permuatation
 int[] temp = new int[n];
 for (int i = 0; i < n; ++i)
 {
 temp[i] = ++factoradic[i];
 }
 this.data[n - 1] = 1; // right-most element is set to 1.
 for (int i = n - 2; i >= 0; --i)
 {
 this.data[i] = temp[i];
 for (int j = i + 1; j < n; ++j)
 {
 if (this.data[j] >= this.data[i])
 ++this.data[j];
 }
 }
 for (int i = 0; i < n; ++i) // put in 0-based form
 {
 --this.data[i];
 }
 } // Permutation(n,k)
 private Permutation(int[] a)
 {
 this.data = new int[a.Length];
 a.CopyTo(this.data, 0);
 this.order = a.Length;
 }
 public int Order
 {
 get
 {
 return this.order;
 }
 }
 public Object[] ApplyTo(Object[] arr)
 {
 Object[] result = new Object[arr.Length];
 for (int i = 0; i < result.Length; ++i)
 {
 result[i] = arr.GetValue(this.data[i]);
 }
 return result;
 }
 public Permutation Next()
 {
 Permutation result = new Permutation(this.order);
 int left, right;
 for (int k = 0; k < result.order; ++k) // Step #0 - copy current data into result
 {
 result.data[k] = this.data[k];
 }
 left = result.order - 2; // Step #1 - Find left value 
 while ((result.data[left] > result.data[left + 1]) && (left >= 1))
 {
 --left;
 }
 if ((left == 0) && (this.data[left] > this.data[left + 1]))
 return null;
 right = result.order - 1; // Step #2 - find right; first value > left
 while (result.data[left] > result.data[right])
 {
 --right;
 }
 int temp = result.data[left]; // Step #3 - swap [left] and [right]
 result.data[left] = result.data[right];
 result.data[right] = temp;
 int i = left + 1; // Step #4 - order the tail
 int j = result.order - 1;
 while (i < j)
 {
 temp = result.data[i];
 result.data[i++] = result.data[j];
 result.data[j--] = temp;
 }
 return result;
 }
 public Permutation Element(int n)
 {
 int[] result = new int[data.Length];
 int[] factoradic = new int[data.Length];
 // Find the factoradic
 for (int i = 1; i <= data.Length; i++)
 {
 factoradic[data.Length - i] = n % i;
 n /= i;
 }
 // Convert the factoradic to the permutation
 IList<int> tempList = new List<int>(data);
 for (int i = 0; i < data.Length; i++)
 {
 result[i] = tempList[factoradic[i]];
 tempList.RemoveAt(factoradic[i]);
 }
 return new Permutation(result);
 }
 public Permutation this[int n]
 {
 get { return this.Element(n); }
 }
 public static ArrayList Generate(Object[] list, bool random)
 {
 Permutation p = new Permutation(list.Length);
 ArrayList result = new ArrayList();
 if (random){
 int permNum = new Random().Next(Util.Factorial(list.Length));
 result.Add( p[permNum].ApplyTo(list));
 } else {
 while (p != null) {
 result.Add(p.ApplyTo(list));
 p = p.Next();
 }
 }
 return result;
 }
}
public class Combination
{
 private int n = 0;
 private int k = 0;
 private int[] data = null;
 public Combination(int n, int k)
 {
 this.n = n;
 this.k = k;
 this.data = new int[k];
 for (int i = 0; i < k; ++i)
 this.data[i] = i;
 } // Combination(n,k)
 public Combination(int n, int k, int[] a) // Combination from a[]
 {
 this.n = n;
 this.k = k;
 this.data = new int[k];
 for (int i = 0; i < a.Length; ++i)
 this.data[i] = a[i];
 } // Combination(n,k,a)
 public bool IsValid()
 {
 if (this.data.Length != this.k)
 return false; // corrupted
 for (int i = 0; i < this.k; ++i)
 {
 if (this.data[i] < 0 || this.data[i] > this.n - 1)
 return false; // value out of range
 for (int j = i + 1; j < this.k; ++j)
 if (this.data[i] >= this.data[j])
 return false; // duplicate or not lexicographic
 }
 return true;
 } // IsValid()
 public Combination Next()
 {
 if (this.data[0] == this.n - this.k)
 return null;
 Combination ans = new Combination(this.n, this.k);
 int i;
 for (i = 0; i < this.k; ++i)
 ans.data[i] = this.data[i];
 for (i = this.k - 1; i > 0 && ans.data[i] == this.n - this.k + i; --i)
 ;
 ++ans.data[i];
 for (int j = i; j < this.k - 1; ++j)
 ans.data[j + 1] = ans.data[j] + 1;
 return ans;
 } // Successor()
 public Combination First()
 {
 Combination ans = new Combination(this.n, this.k);
 for (int i = 0; i < ans.k; ++i)
 ans.data[i] = i;
 return ans;
 } // First()
 public Object[] ApplyTo(Array arr)
 {
 Object[] result = new Object[arr.Length];
 for (int i = 0; i < result.Length; ++i)
 {
 result[i] = arr.GetValue(this.data[i]);
 }
 return result;
 }
 public Object[] ApplyTo(Object[] strarr)
 {
 Object[] result = new Object[this.k];
 for (int i = 0; i < result.Length; ++i)
 result[i] = strarr[this.data[i]];
 return result;
 } // ApplyTo()
 public static int Choose(int n, int k)
 {
 if (n < k)
 return 0; // special case
 if (n == k)
 return 1;
 int delta, iMax;
 if (k < n - k) // ex: Choose(100,3)
 {
 delta = n - k;
 iMax = k;
 }
 else // ex: Choose(100,97)
 {
 delta = k;
 iMax = n - k;
 }
 int ans = delta + 1;
 for (int i = 2; i <= iMax; ++i)
 {
 checked { ans = (ans * (delta + i)) / i; } // Throws OverFlow Exception
 }
 return ans;
 } // Choose()
 // return the mth lexicographic element of combination C(n,k)
 public Combination Element(int m)
 {
 int[] ans = new int[this.k];
 int a = this.n;
 int b = this.k;
 int x = (Choose(this.n, this.k) - 1) - m; // x is the "dual" of m
 for (int i = 0; i < this.k; ++i)
 {
 ans[i] = LargestV(a, b, x); // largest value v, where v < a and vCb < x 
 x = x - Choose(ans[i], b);
 a = ans[i];
 b = b - 1;
 }
 for (int i = 0; i < this.k; ++i)
 {
 ans[i] = (n - 1) - ans[i];
 }
 return new Combination(this.n, this.k, ans);
 } // Element()
 public Combination this[int m]
 {
 get { return this.Element(m); }
 }
 // return largest value v where v < a and Choose(v,b) <= x
 private static int LargestV(int a, int b, int x)
 {
 int v = a - 1;
 while (Choose(v, b) > x)
 --v;
 return v;
 } // LargestV()
 public static ArrayList Generate(Object[] list, int choose, bool random)
 {
 Combination c = new Combination(list.Length, choose);
 ArrayList result = new ArrayList();
 if (random)
 {
 int permNum = new Random().Next(Util.Combination(list.Length, choose));
 result.Add(c[permNum].ApplyTo(list));
 }
 else
 {
 while (c != null)
 {
 result.Add(c.ApplyTo(list));
 c = c.Next();
 }
 }
 return result;
 }
}
public class Variation
{
 //public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
 //{
 // IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
 // return sequences.Aggregate(
 // emptyProduct,
 // (accumulator, sequence) =>
 // from accseq in accumulator
 // from item in sequence
 // select accseq.Concat(new[] { item }));
 //}
 public static ArrayList Generate(Object[][] lists)
 {
 int seqCount = lists.Length;
 ArrayList accum = new ArrayList(seqCount);
 if (seqCount > 0)
 {
 Stack enumStack = new Stack();
 Stack itemStack = new Stack();
 int index = seqCount - 1;
 IEnumerator enumerator = lists[index].GetEnumerator();
 while (true)
 if (enumerator.MoveNext())
 {
 itemStack.Push(enumerator.Current);
 if (index == 0)
 {
 accum.Add(itemStack.ToArray());
 itemStack.Pop();
 }
 else
 {
 enumStack.Push(enumerator);
 enumerator = lists[--index].GetEnumerator();
 }
 }
 else
 {
 if (++index == seqCount)
 break;
 itemStack.Pop();
 enumerator = enumStack.Pop() as IEnumerator;
 }
 }
 return accum;
 }
}
public class Util
{
 public static int Factorial(int n)
 {
 int f = 1;
 while (n > 1) { f *= n; --n; }
 return f;
 }
 public static int Combination(int n, int k)
 {
 return Factorial(n) / (Factorial(k) * Factorial(n - k));
 }
}
}

• sepp2k: Did you tag this as functional-programming because you want to take the code into a more functional direction? Otherwise I don't see the reason for the tag, this code is as imperative as it gets.
• sepp2k: Ok, this is a lot of code. Some comments and documentation for the various methods as well as a description of how you're using (or planning on using) the code and an explanation of your design decisions would greatly help people to give you meaningful advice.

Answer 1

1. Why have you commented out Linq namespace? Use it at least here:

   this.data = new int[n];
   for (int i = 0; i < n; ++i)
   {
    this.data[i] = i;
   }
   

   It can be replaced with:

   this.data = Enumerable.Range(0, n).ToArray();
   

2. In first two Permutation constructors you have:

   public Permutation(int n)
   {
    this.data = new int[n];
    ...
    this.order = n;
   }
   public Permutation(int n, int k)
   {
    this.data = new int[n];
    this.order = this.data.Length;
    ...
   }
   

   Effectively, order is being set to the same value, but you're doing it in a different way in similar scenarios. This makes it more confusing. Either use order = n in both places or use order = data.Length. Keep it consistent.

3. In the Permutation class, you have field order which is always set to be a length of data and you also have a property to retrieve this field. I believe this additional field makes this code more error prone because you have to remember to set this field. I would remove it and replace Order property to return data.Length.

4. In many places, it is unclear what's going on and how to use these classes. Add some documentation. I would never guess how Permutation.Element(n) would return new Permutation.

5. This statement in the second Permutation constructor is misleading:

   for (int i = 0; i < n; ++i)
   {
    temp[i] = ++factoradic[i]; // <-- Why ++ ???
   }
   

   I would remove ++ here. In this way it makes me think that factoradic[i] is used somewhere else, but it is not. Use factoradic[i] + 1 instead. Remember that when somebody will read/review your code he will have to keep in mind all the variables in method. This line just made this reviewer to update variable value which is not a cheap operation for people.

   Also consider using LINQ here and replace it with:

   int[] temp = factoradiac.Select(i => i + 1).ToArray();
   

I wasn't strong enough to read through second class, so probably some my points will be applicable there also.

Answer 2

A couple of things that I've noticed (though I haven't worked through all of the code in detail):

public Object[] ApplyTo(Object[] arr)

Again I don't know how this is going to be used, but this looks suspiciously as if you were doing something like Foo[] myFoos = (Foo[]) myPermutation.ApplyTo(oldFoos), which is bad. You should make ApplyTo generic, so you don't need to cast the returned array back to the original type.

---

result[i] = arr.GetValue(this.data[i]);

I don't see why you use GetValue instead of [] here.

---

public Permutation Next()

It might be nicer to have a static method which returns an enumerable of all the permutations instead of having to call the Next method all the time. Though of course that depends on how it is used.

---

public Object[] ApplyTo(Array arr)
{
 Object[] result = new Object[arr.Length];
 for (int i = 0; i < result.Length; ++i)
 {
 result[i] = arr.GetValue(this.data[i]);
 }
 return result;
}

The only reason that comes to mind why it'd make sense to take Array rather than Object[] (or better yet: generics) here, would be to work with arrays of arbitrary dimensions. However the code will only work with one-dimensional arrays, so this overload seems completely superfluous to me.

---

public static int Factorial(int n)
{
 int f = 1;
 while (n > 1) { f *= n; --n; }
 return f;
}

The backwards-counting while-loop seems harder to understand than a plain forward-counting for-loop to me. Or you could define it using LINQ's Aggregate method (you did tag this "functional programming" after all).

Also I'd put the main logic into a method int Product(int from, int to) which multiplies the numbers from from to to and then just call that as Product(1, n) to define Factorial.

---

public static int Combination(int n, int k)
{
 return Factorial(n) / (Factorial(k) * Factorial(n - k));
}

This seems to be a less optimized reimplementation of Permutation.Choose, I don't see why you'd need this method twice.

That said you can optimize this version a bit by using the fact that x! / y! is the product of the numbers from k+1 to n (using my suggested Product method):

return Product(k+1, n) * Factorial(n-k);

This way the method does slightly less work and can work with more numbers without overflowing, while still being as concise as before.

• Snowbear: I'll try to guess what ApplyTo means. I believe it returns an array which will have the same items as original but in order determined by this permutation. You pass in Red, Orange, Yellow, Green, LightBlue, Blue, Violet and receive smth like Yellow, Blue, Green, Orange, Red, Violet, LightBlue
• Snowbear: Also regarding static method to return an enumerable of all permutations I would mention that probably it should be lazy and implemented with yield return in order to be more memory efficient
• sepp2k: @Snowbear: Yes, it should, +1 for pointing that out. Regarding ApplyTo I can see what it does - I said "I don't know how this is going to be used" because I don't know whether he's only going to call it with arrays whose type actually is Object[], in which case not using generics is okay, or (the more likely case) he's using it with more arrays of more specific types and then casting, in which case he should definitely use generics.
• user2678: Thanks for the detailed review. This code will be used to randomize running some automated test cases. I would agree I could use more Linq and generics and add more comments. I am new to C# and coding and this was my first try. Next time I will try to post less code for review.

Answer 3

As far as I can see, order is always data.Length.

 this.data = new int[n];
 this.order = this.data.Length;

So I would remove it, because there is only the chance to forget to update it somewhere.

I would wish more documentation too: How is the class supposed to be used. From a functional approach I would expect more recursive methods, but it's unclear, how restrictive you're bound to some interface.