Skip to content

Instantly share code, notes, and snippets.

@ane
Created June 19, 2011 19:51
Show Gist options
  • Save ane/1034657 to your computer and use it in GitHub Desktop.
Save ane/1034657 to your computer and use it in GitHub Desktop.
Permutations by Ehrlich swaps
static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> collection)
{
// Initialize
int length = collection.Count();
int[] b = Enumerable.Range(0, length).ToArray();
// Set all in c to zero.
int[] c = Enumerable.Range(0, length + 1).Select(x => 0).ToArray();
// Create a temporary copy.
List<T> set = collection.Select(x => x).ToList();
while (true)
{
// Return the permutation.
yield return set;
int k = 1;
// Find k.
while (c[k] == k)
{
c[k] = 0;
k++;
}
// Termination if k == n.
if (k == length)
yield break;
c[k]++;
// Swap a[0] <-> a[b[k]].
T tmp = set[0];
set[0] = set[b[k]];
set[b[k]] = tmp;
// Flip contents.
set.Reverse(1, k - 1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment