How to get Linq to generate all arrays of length n*n containing all permutations of 1..n

Question

Please note that this is not yet another "how to generate all permutations" question, of which there are loads here. I have looked at plenty of those and am no further in my specific question.

Given an integer n, I would like to generate a List<int[]> of int[n*n] where each list contains a unique permutation of the integers from 1 to n.

So if n were 2, I would want to see 16 arrays, as follows...

[1,1,1,1],
[1,1,1,2],
[1,1,1,3],
[1,1,1,4],
[1,1,2,1],
[1,1,2,2],
...etc
[4,4,4,1],
[4,4,4,2],
[4,4,4,3],
[4,4,4,4],

For this specific case, it could be achieved with the following...

Enumerable.Range(1, 2)
  .SelectMany(n1 => Enumerable.Range(1, 2)
    .SelectMany(n2 => Enumerable.Range(1, 2)
      .SelectMany(n3 => Enumerable.Range(1, 2)
        .Select(n4 => new[] { n1, n2, n3, n4 }))))
  .ToList()

However, apart from being unwieldly, this is hard-coded for the number 2. If I wanted to do the same for 3, I'd need to have 9 SelectMany lines and so on. I would like a flexible solution that would work for whatever number were passed in.

All the other questions I've seen just want all permutations of 1 to n, ie a collection of n arrays, each of length n. My situation requires n*n arrays, each of length n*n.

Anyone able to help? Thanks

Answer 1

My situation requires n*n arrays, each of length n*n.

Based on your own description of your situation (and your code snippet for n = 2), this is not correct.

Your situation requires n^(n*n) arrays, each of length n*n:

Max value n	Array length n*n	Array count n^(n*n)
1	1	1
2	4	16
3	9	19683
4	16	4294967296
5	25	Oh my

As we can see, this escalates extremely quickly. Hence,

I would like a flexible solution that would work for whatever number were passed in.

is a rather unrealistic goal, in my opinion.

---

I did find this a fun challenge, though, and I will present my take on it, which works for n = { 1, 2, 3 }.
(n = 4 produces an Out of memory.)

The logic of my implementation is basically:

1. Calculate the size of each array (size)
2. Calculate the size of the resulting list (permutationCount)
3. Create a placeholder array, which temporarily holds the values of an array that is to be added to the resulting list (placeholder)
4. Populate the resulting list with the very first array
   (for n = 1, the first (and only) array is [1])
   (for n = 2, the first array is [1, 1, 1, 1])
   (for n = 3, the first array is [1, 1, 1, 1, 1, 1, 1, 1, 1])
5. Populate the resulting list with the remaining arrays

In the very last step, we iterate through each index of placeholder and check whether we need to update the value at the given index. We need to update the value at a given index when one of two scenarios occur:

1. it is the last index
2. every succeeding value in placeholder (which have not yet been updated, seeing as we are iterating placeholder and conditionally updating the value from beginning to end) has the maximal possible value. (The maximal possible value is n)

The act of updating a value will always follow the same rules:

• if the old value is lower than the maximal possible value (n): Increase the value by 1
• if the old value is equal to the maximal possible value (n): Reset the value to 1

As an example: For max value = n = 3, the logic would be as follows:

old value	new value
1	2
2	3
3	1

Calculating the new value based on the old value and the max value can be achieved in a straight forward manner by using the modulo operator (%):

newValue = 1 + (oldValue % maxValue)

After the value of all indices of placeholder have been evaluated (and conditionally updated), an array with those values are added to the resulting list.

---

And now, to the actual code:

I have wrapped the logic inside a method, which can be called with the desired max value.
(max is your n.)

private static List<int[]> GetAllUniquePermutationsOfTheIntegersFrom1To(int max)
{
    const int min = 1;

    int size = max * max;
    int lastIndex = size - 1;
    
    double permutationCount = Math.Pow(max, size);
    
    var placeholder = new int[size];
    Array.Fill(placeholder, min);
    
    var result = new List<int[]> { placeholder.ToArray() };
    
    var isLastEntry =
        (int i) => i == lastIndex;
    var allSucceedingEntriesHaveReachedMaxValue =
        (int i) => placeholder[(i + 1)..].All(entry => entry == max);
    
    while (result.Count < permutationCount)
    {
        for (var i = 0; i < size; i++)
        {
            if (isLastEntry(i) || allSucceedingEntriesHaveReachedMaxValue(i))
            {
                placeholder[i] = 1 + (placeholder[i] % max);
            }
        }
        
        result.Add(placeholder.ToArray());
    }
    
    return result;
}

Calling the method with max = 2 and writing the results to the console

var uniquePermutations = GetAllUniquePermutationsOfTheIntegersFrom1To(2);

foreach (var entry in uniquePermutations)
{
    Console.WriteLine(string.Join(", ", entry));
}

produces:

1, 1, 1, 1
1, 1, 1, 2
1, 1, 2, 1
1, 1, 2, 2
1, 2, 1, 1
1, 2, 1, 2
1, 2, 2, 1
1, 2, 2, 2
2, 1, 1, 1
2, 1, 1, 2
2, 1, 2, 1
2, 1, 2, 2
2, 2, 1, 1
2, 2, 1, 2
2, 2, 2, 1
2, 2, 2, 2

If nothing else, I hope this can give you some inspiration to build on further, for your own implementation.

Example fiddle is found here.