Efficient way of doing ordered permutations

Question

I don't know if it's possible, but I'm trying to find, in C#, an algorithm which can generate all the permutations of a set of number with some "empty space" in it while keeping its order.

Example :

I have an array [1,2] and I need all the ordered permutations with two "Empty space". In this case, I will have :

[1,2,null,null]
[1,null,2,null]
[1,null,null,2]
[null,1,2,null]
[null,1,null,2]
[null,null,1,2]

I have tried to include all the "empty space" inside the array before doing a permutation, but it yield too much permutations that I do not need.

in C#, the function could be

    private static List<int[]> PermutateWithSpace(this List<int> set, int numberOfEmptySpace)
    {
        // Algorithm which yield all possible permutations of my N "null" inside my set
    }

It's unclear what algorithm definition is. I.e. what determines how many empty spaces you have, is it just empty spaces that are being shuffled around? In your example `[1,null,null,2]` appears twice - why and what rule in the algorithm describes duplication? — LB2, Jun 06 '17 at 14:11
Go up one level if you can. You're probably not doing this for fun but because some other algorithm needs this as its input, right? Is there any way you can simply make that cleverer by inserting the `null` as required while it's reading the input? At least preserving the order there should be easier. — Jeroen Mostert, Jun 06 '17 at 14:11
This is answered in [Permutation of array](https://stackoverflow.com/questions/2920315/permutation-of-array) since nulls can just be treated as repeated characters. Just Google "generate permutations with repetition". — Bernhard Barker, Jun 06 '17 at 14:32
Your question is a little confusing because you have listed all the permutations *twice*. There are only six such permutations, but you've listed twelve. — Eric Lippert, Jun 06 '17 at 14:40
@Dukeling generating raw permutation could do the tricks, but I could have a set of 8 elements with 10 null. Generating a raw permutation for 18 elements will yield 6402373705728000 possibilities, it's too much — KDelli, Jun 06 '17 at 14:55
@KDelli The highest-voted (not accepted) answer to the linked post seems to explain how to generate non-unique permutations, i.e. for 8 unique elements and 10 nulls, you'd have 18!/10! = 1764322560 permutations. If that's still too much, you need to tell us **why** - there **are** that many permutations, and based on your question, you seem to want **all** of them - if this is not the case, you don't just want to generate ordinary permutations any more and you need to specify according to what criteria they should be excluded. — Bernhard Barker, Jun 06 '17 at 15:00
Notice that my approach in the accepted answer produces *one permutation at a time*, and not *all of them at once*. Plainly if there are a bazillion possible permutations you do not want to try to realize them all in a list. — Eric Lippert, Jun 06 '17 at 16:26

Eric Lippert · Accepted Answer · 2017-06-06T16:25:09.513

Sure, that algorithm is straightforward.

Suppose you have n numbers and m nulls. We're going to start with the nulls and then insert the numbers as we go.

The first thing we do is figure out where the first number goes. We yield 0, 1, 2, ... m nulls, and then yield the first number.

Suppose we yielded x nulls on this permutation. Now we figure out where the second number goes. We yield 0, 1, 2, ... m - x nulls, and then yield the second number.

And so on.

Is that enough of a hint, or do you need to see the algorithm written out?

In case you get stuck:

static IEnumerable<T> Append<T>(this IEnumerable<T> items, T item) 
{
    foreach(var i in items)
        yield return i;
    yield return item;
}

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls)
{
    if (min > max)
        yield return Enumerable.Repeat<int?>(null, nulls);
    else
        for(int i = 0; i <= nulls; ++i)
            foreach(var r in DoIt(min + 1, max, nulls - i))
                yield return Enumerable.Repeat<int?>(null, i).Append(min).Concat(r);    
}

Or, even more compactly, in LINQ style!

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls)
{
    return (min > max) ? 
        new[] { Enumerable.Repeat<int?>(null, nulls) } :
        from i in Enumerable.Range(0, nulls + 1)
        from r in DoIt(min + 1, max, nulls - i)
        select Enumerable.Repeat<int?>(null, i).Append(min).Concat(r);
}

Thanks ! I'll try to write a C# algorithm with your hint. – KDelli Jun 06 '17 at 14:27 — KDelli, Jun 06 '17 at 14:27
Works like a charm ! Incredibly fast by the way – KDelli Jun 06 '17 at 15:47 — KDelli, Jun 06 '17 at 15:47

Efficient way of doing ordered permutations

1 Answers1