How to use query syntax to create permutations?

Question

I tried to write a method that returns the permutation of a given enumeration as simple as possible. Code:

using System.Collections.Generic; public static partial class Permutable { static IEnumerable<IEnumerable<T>> PermuteIterator<T>( IEnumerable<T> source, int offset) { var count=0; foreach(var dummy in source) if(++count>offset) foreach( var sequence in Permutable.PermuteIterator( source.Exchange(offset, count-1), 1+offset) ) yield return sequence; if(offset==count-1) yield return source; } public static IEnumerable<IEnumerable<T>> AsPermutable<T>( this IEnumerable<T> source) { return Permutable.PermuteIterator(source, 0); } public static IEnumerable<T> Exchange<T>( this IEnumerable<T> source, int index1, int index2) { // exchange elements at index1 and index2 } } 

Once the code has simplified into an iterator block, I try to make it just a single LINQ query expression.

There is recursion in the nested foreach with this code, even another one may go beyond the foreach ; and this is the hard part for me to rewrite it in the query syntax.

I read this answer:

Rearrange Strings in C #

But I think this is not a solution for me ..

I tried different ways, and I think that it is not so easy to do. How can i do this?

(The Exchange method is another issue, and I asked a question:

How to exchange enumeration elements by exchanging only once?

But I think that is not the case.)

Answer 1

EDIT 1:

Single line solution without recursion

I repeated the main method (from the previous solution below in this answer), so now it is no longer recursive. Now it’s easy to make a one-line solution.

I had to use Enumerable methods and extension methods to do this. Without them, I think that it is impossible to do.

 class Permutator { private static IEnumerable<IEnumerable<int>> CreateIndices(int length) { var factorial = Enumerable.Range(2, length - 1) .Aggregate((a, b) => a * b); return (from p in Enumerable.Range(0, factorial) // creating module values from 2 up to length // eg length = 3: mods = [ p%2, p%3 ] // eg length = 4: mods = [ p%2, p%3, p%4 ] let mods = Enumerable.Range(2, length - 1) .Select(m => p % m).ToArray() select ( // creating indices for each permutation mods.Aggregate( new[] { 0 }, (s, i) => s.Take(i) .Concat(new[] { s.Length }) .Concat(s.Skip(i)).ToArray()) )); } public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { var array = items.ToArray(); return from indices in CreateIndices(array.Length) select (from i in indices select array[i]); } } 

Now the final decision

The result is this monster:

 class Permutator { public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { return from p in Enumerable.Range(0, Enumerable.Range(2, items.Count() - 1) .Aggregate((a, b) => a * b)) let mods = Enumerable.Range(2, items.Count() - 1) .Select(m => p % m).ToArray() select mods.Aggregate( items.Take(1).ToArray(), (s, i) => s.Take(i) .Concat(items.Skip(s.Length).Take(1)) .Concat(s.Skip(i)).ToArray()); } } 

Previous decision

I created something that might be what you are looking for:

 class Permutator { private static IEnumerable<IEnumerable<int>> CreateIndices(int length) { return (from p in Enumerable.Range(0, length) select ( from s in Permutator.CreateIndices(length - 1) .DefaultIfEmpty(Enumerable.Empty<int>()) select s.Take(p) .Concat(new[] { length - 1 }) .Concat(s.Skip(p)) )) .SelectMany(i => i); } public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items) { var array = items.ToArray(); return from indices in CreateIndices(array.Length) select (from i in indices select array[i]); } } 

Usage example:

 var items = new[] { "0", "1", "2" }; var p = Permutator.Get(items); var result = p.Select(a=>a.ToArray()).ToArray(); 

How it works

The kernel is the CreateIndices method. It creates a sequence containing the indices of the source elements for each permutation.

Best explained with an example:

 CreateIndices(0); // returns no permutations CreateIndices(1); // returns 1 permutation // [ 0 ] CreateIndices(2); // returns 2 permutations // [ 1, 0 ] // [ 0, 1 ] CreateIndices(3); // returns 6 permutations // [ 2, 1, 0 ] // [ 2, 0, 1 ] // [ 1, 2, 0 ] // [ 0, 2, 1 ] // [ 1, 0, 2 ] // [ 0, 1, 2 ] 

This is a recursive method based only on enumerated extensions and LINQ syntax queries.

The idea of ​​recursion is that each level builds on the basis of the previous one.

CreateIndices(n) adds element n-1 to the permutations returned by CreateIndices(n-1) at all available positions.

CreateIndices(0) recursion root returns an empty set of permutations.

Explanation in stages: CreateIndices(3)

1. Let's start by creating the result of CreateIndices(0) :

• empty

2. Then the result of CreateIndices(1) :

• add element 0 (n-1) to each of the previous substitutions, at position 0
  [0]

3. Then the result of CreateIndices(2)

• add element 1 (n-1) to each of the previous permutations, at position 0
  [ten]
• add element 1 (n-1) to each of the previous permutations, at position 1
  [0, 1]

4. Then the result of CreateIndices(3)

• add element 2 (n-1) to each of the previous substitutions, at position 0
  [2, 1, 0]
  [2, 0, 1]
• add element 2 (n-1) to each of the previous substitutions, at position 1
  [1, 2, 0]
  [0, 2, 1]
• add element 2 (n-1) to each of the previous substitutions, at position 2
  [1, 0, 2]
  [0, 1, 2]

What will happen next

Now that we have indexes for each of the permutations, we can use them to construct real permutations of values. This is what the general Get method does.

Also note that the Get method is the only one that materializes the original sequence into an array. CreateIndices is just an enumerator, without any real objects ... so you only list costs when listing sequences and when you call Get , which you pay to create an array of the original sequence.

This explains why, after calling Get in this example, I had to materialize the result so that we could use it:

 var items = new[] { "0", "1", "2" }; var p = Permutator.Get(items); // pay to create array from source elements var result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations ).ToArray(); // pay to get the permutations 

This allows us to pay only half the cost if we simply list half the permutations.

Answer 2

Since you are looking for an answer that uses existing LINQ query operators rather than using iterator blocks, here is one. Please note that this will not be as effective as some other solutions; using these query operators is not as efficient as, say, Eric Lippert's solution. (It's a lot shorter though.)

Also note that since this solution uses SelectMany and Where overloads that accept an index, these statements must be invoked using the method syntax rather than the query syntax, and some of the other statements do not have syntax equivalents. I could change one Select to the query syntax, but for consistency I did not.

 public static IEnumerable<IEnumerable<T>> Permuatations<T>( this IEnumerable<T> source) { var list = source.ToList();//becase we iterate it multiple times return list.SelectMany((item, i) => list.Where((_, index) => index != i) .Permuatations() .Select(subsequence => new[] { item }.Concat(subsequence))) .DefaultIfEmpty(Enumerable.Empty<T>()); } 

So, let's talk about what this does.

First, it goes through the original sequence; for each element in this sequence, it creates a sequence that is similar to the original sequence, but with the "current element" displayed. (This is the list.Where method).

Then it (recursively) gets all the permutations of this subsequence.

After that, he adds the “deleted” element to the beginning of each of these subsequences.

All of these subsequences are flattened together since they are all inside SelectMany .

DefaultIfEmpty exists to ensure that the outer sequence is never empty. Carrying an empty sequence results in a sequence with an empty sequence inside it. This is effectively the "base case" of a recursive operation.

Answer 3

Old as me, I never like recursion when it's not needed.

Since you need to iterate the source anyway, I just store it in an array. I track an array of "swappings" that tells the program what to change; the index is the initial position of the swap, the index is the destination.

You can also do sub-permutations if you want.

If you really feel comfortable with pain, I think you can also change swaps to sophisticated Exchange IEnumerable; I think this is a good way to add a lot of complexity, while at the same time making things slower. :-)

I also reuse the array; it seems foolish to repeat everything every time, which saves you a lot of time copying data and doing recursion when "src" is big. It is quite effective.

 public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> src) { T[] array = src.ToArray(); // Initialize int[] swappings = new int[array.Length]; for (int j = 0; j < array.Length; ++j) { swappings[j] = j; } yield return array; int i = swappings.Length - 2; while (i >= 0) { int prev = swappings[i]; Swap(array, i, prev); int next = prev + 1; swappings[i] = next; Swap(array, i, next); yield return array; // Prepare next i = swappings.Length - 1; while (i >= 0 && swappings[i] == array.Length - 1) { // Undo the swap represented by permSwappings[i] Swap(array, i, swappings[i]); swappings[i] = i; i--; } } } private static void Swap<T>(T[] array, int i, int next) { var tmp = array[i]; array[i] = array[next]; array[next] = tmp; }