Recursive iterator performance, part 3

re: Recursive iterator performance, part 3

Alexandr K. — Sat, 22 Mar 2008 14:51:16 GMT

I forget my simple Swap function :-D

#region . Swap 2 elements in Array .

private static void Swap<T>(List<T> arr, int pos1, int pos2)

{

if (pos1 != pos2)

{

T temp = arr[pos1]; arr[pos1] = arr[pos2]; arr[pos2] = temp;

}

#endregion

re: Recursive iterator performance, part 3

Alexandr K. — Sat, 22 Mar 2008 14:49:14 GMT

#region . Permute .

public static IEnumerable<List<T>> Permute<T>(List<T> arr)

{

foreach (List<T> permutedArr in Permute(arr, 0, arr.Count - 1))

{

yield return permutedArr;

}

private static IEnumerable<List<T>> Permute<T>(List<T> arr, int lowerBound, int upperBound)

{

if (lowerBound == upperBound) yield return arr;

else

{

for (int i = lowerBound; i <= upperBound; i++)

{

Swap(arr, i, lowerBound);

foreach (List<T> permutedArr in Permute(arr, lowerBound + 1, upperBound))

{

yield return permutedArr;

}

Swap(arr, i, lowerBound);

}

#endregion

public permutationsForm()

{

InitializeComponent();

}

private void buttonPermute_Click(object sender, EventArgs e)

{

List<string> array = new List<string>();

array.AddRange( textPermuteSize.Text.Split(' ') );

foreach (List<string> s in Permute<string>(array))

{

foreach (string s1 in s)

textPremutations.Text += s1;

textPremutations.Text += "; ";

}

I disagree

warsaw hotels — Tue, 14 Aug 2007 20:33:42 GMT

Last week and weekend I discussed performance of iterators in C# 2.0, specifically recursive iterators.Recursive iterator performanceRecursive iterator performance, part 2

I do not agree. Go to http://apartments.waw.pl/

re: Recursive iterator performance, part 3

Stephen Toub — Thu, 04 Nov 2004 23:37:00 GMT

Of course, there are a plethora of ways to implement a permutation enumeration, some that use recursion and some that don't, some that maintain lexicographical ordering, some that maintain other orderings, etc. The code you show above doesn't compile (and fixing the compiler errors appropriately results in IndexOutOfRange exceptions being thrown at runtime), but I think you intended something like the following which does work correctly:

public static IEnumerable<T[]> Permute<T>(T[] arr) where T : IComparable
{
Array.Sort(arr);
int upperBound = arr.Length - 1;
while (true)
{
yield return arr;

int i, j;
for (i = upperBound - 1; i >= 0 && arr[i].CompareTo(arr[i + 1]) > 0; i--);
if (i < 0) break;

for (j = upperBound; arr[i].CompareTo(arr[j]) > 0; j--) ;

Swap(arr, i, j);
Array.Reverse(arr, i + 1, upperBound - i);
}
}

Note that I've restricted the generic T parameter to be an IComparable so that I can use the CompareTo method on each element of the array (operators won't work).

In the previous recursive->iterative example I was just demonstrating one way to do it, and more specifically showing that there's a pattern you can follow to go from recursive to iterative. That doesn't mean it's always something you want to do, as I've mentioned.

In any event, if you're interested in permutation algorithms, Robert Sedgewick wrote a good survey of a bunch of them in the 70s, and it's available at http://portal.acm.org/ft_gateway.cfm?id=356692&type=pdf.

re: Recursive iterator performance, part 3

Steve Newman — Thu, 04 Nov 2004 21:41:00 GMT

Sometimes, there's an iterative algorithm that doesn't require a stack. Iterating over permutations is an example:

public static IEnumerable<T[]> Permute<T>(T[] arr)
{
Array.Sort(arr);
while (true)
{
yield return arr;
for (int i=arr.Length-2; ; i--)
if (arr[i] < arr[i+1])
{
Array.Reverse(arr, i+1, arr.Length-i-1);
for (int j=i+1; ; j++)
if (arr[i] < arr[j])
{ T t = arr[i]; arr[i] = arr[j]; arr[j] = t; break; }

break;
}
else if (i == 0)
return;
}
}

This algorithm has the advantages of returning the permutations in lexicographic order, and it works even if the array has duplicate entries (each unique permutation is only returned once). It does require that T define a sorting order. (Meaning that it won't compile as written -- T needs to be restricted to IComparable, and it should use CompareTo instead of the < and > operators. Apologies, I don't have access to a C# 2.0 compiler -- this code is adapted from an algorithm to permute ints.)