Here is a Permuted Order class to find the next permutation of any ArrayList
using Lexicographic order based on HashCodes.
I would prefer to use Object Reference int as the order key as would not
have to call GetHashCode() on each object in arraylist, but can't figure out
a way to get object ref int in a safe context. Maybe not good either as GC
can move refs - right?
Note the Array itself keeps the "state" (i.e. the current order of its
objects) so Methods can be static as done here. A call to GetNext(array),
just moves around objects in the Array to give you next permuted
combination. This is nice as you don't have to build all combinations first
and you can add and remove items as needed.
You can have duplicate objects (i.e. duplicate hashcodes) in the array or
add or delete objects from array and function will still work, but may sort
the array again to start perms from top again. If all hashcodes are unique,
number of permutations is factorial of unique items. If have some dup
items, number of permutations depends on number of unique items, number of
dup items, etc. For example, try the following with ArrayList of {1,2,3}
and {0,0,1} to see the difference. First will yield 6 combinations, second
will yield 3 (not 2 or 6 as you may first think.) Anyway, here is the code.
Cheers!
/// <summary>
/// Summary description for PermutedOrder.
/// </summary>
public class PermutedOrder
{
private static bool reset;
private PermutedOrder()
{
}
internal class HashComparer : IComparer
{
#region IComparer Members
public int Compare(object x, object y)
{
int xHash = x.GetHashCode();
int yHash = y.GetHashCode();
if ( xHash == yHash )
return 0;
if ( xHash < yHash )
return -1;
return 1;
}
#endregion
}
public static void SortArray(ArrayList values)
{
if ( values == null )
throw new ArgumentNullException("values");
if ( values.Count < 2 )
return;
values.Sort(new HashComparer());
}
/// <summary>
/// Find the next permutation using Lexicographic order of hash codes
returned by array objects.
/// Normally, the array would start sorted in hash code order, but is not
required.
/// Adding or deleting elements is ok too as the function will re-sort when
needed.
/// Call GetNext to have array arranged to next permutation. Call GetNext
N number of times
/// to see all permutations of unique objects in array (i.e. unique
hashcodes.)
/// </summary>
/// <param name="values">ArrayList of objects to permutate.</param>
public static void GetNext(ArrayList values)
{
if ( values == null || values.Count < 2 )
return;
int i = values.Count - 1;
while ( values[i-1].GetHashCode() >= values[i].GetHashCode() )
{
i = i - 1;
if ( i == 0 )
{
reset = true;
values.Sort(new HashComparer());
return;
}
}
int j = values.Count;
while ( values[j-1].GetHashCode() <= values[i-1].GetHashCode() )
j = j - 1;
Swap(values, i-1, j-1); // swap values at positions (i-1) and (j-1)
i++;
j = values.Count;
while (i < j)
{
Swap(values, i-1, j-1);
i++;
j--;
}
}
/// <summary>
/// Returns the number of permutations the ArrayList could be ordered by.
/// A simple Factorial function does not work as {0,0,1} would yield 3
perms, not 6.
/// </summary>
/// <param name="values"></param>
/// <returns></returns>
public static int PermutationsCount(ArrayList values)
{
if ( values == null || values.Count == 0 )
return 0;
if ( values.Count == 1 )
return 1;
int permCount = 0;
ArrayList tmp = (ArrayList)values.Clone();
SortArray(tmp);
reset = false;
while( reset == false )
{
GetNext(tmp);
permCount++;
}
return permCount;
}
private static void Swap(ArrayList values, int i, int j)
{
object tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}
} // End PermutedOrder Class
//
// *** Test the class ***
//
private void button20_Click(object sender, System.EventArgs e)
{
ArrayList values = new ArrayList();
// {0,1,2} will yield 6 permutations.
values.Add(0);
values.Add(1);
values.Add(2);
// Try other values to see effect of duplicate objects on permutations.
// Below will yield 3 permutations, not 4.
// values.Add(0);
// values.Add(0);
// values.Add(1);
int permsCount = PermutedOrder.PermutationsCount(values);
Console.WriteLine("Number of Permutations:"+permsCount);
PermutedOrder.SortArray(values);
Console.WriteLine(GetArrayAsString(values));
for(int i = 0; i < permsCount - 1; i++)
{
PermutedOrder.GetNext(values);
Console.WriteLine(GetArrayAsString(values));
}
}
private string GetArrayAsString(ArrayList values)
{
string s = null;
for(int i = 0; i < values.Count; i++)
{
s = s + values[i].ToString() + (( i == values.Count - 1 ) ? "" : ", ");
}
return s;
}
