Permutations with constant prefix numbers

Question

I have an array of integers where each value will have distinct meanings.The first value means the length of permutation, the second value represent the length of initial prefix and rest of integers are single integer that make up prefix of all permutations.

For e.g. if the array has elements {5,2,1,4}
where 5 is the number of elements in the permutation array. and 2 is the length of the integer that will makeup the first 2 elements prefix in the array permutation. 1,4 are the prefix integers i.e. length 2 in 5 element permutation combination so missing elements are 2,3,5 where 1&4 being common prefix across all permutations as below
[14235][14253][14325][14352][14523][14532] where input array is {5,2,1,4}
How to achieve this?

I have below code to get the permutation of one missing elements 2,3 & 5 but I am not getting how to program the entire the solution

      static void Main(string[] args)
    {
       int output;
        int ip1;
        ip1 = Convert.ToInt32(Console.ReadLine());
        int ip2_size = 0;
        ip2_size = Convert.ToInt32(Console.ReadLine());
        int[] ip2 = new int[ip2_size];
        int ip2_item;
        for (int ip2_i = 0; ip2_i < ip2_size; ip2_i++)
        {
            ip2_item = Convert.ToInt32(Console.ReadLine());
            ip2[ip2_i] = ip2_item;
        }
        output = correctResult(ip1, ip2);
        Console.WriteLine(output);


    }

      static int correctResult(int n, int[] arr)
      {
        int permLength = 0;
        int prefLength = 0;
        int result = 0;
        permLength = n;
        prefLength = arr.Length;
        int[] permArray = new int[permLength];
        int len = 0;

        var missingNum = Enumerable.Range(1, 
         permLength).Except(arr).ToArray<int>();
        if (permLength < (missingNum.Length + len))
        {
            result = -1;
        }
        else
        {
            for (int i = 0; i < missingNum.Length; i++)
            {
                permArray[prefLength + i] = missingNum[i];
            }
            result = permute(missingNum, 0, missingNum.Length - 1);
        }

        return result;



    }


     static int permute(int[] arry, int i, int n)
        {
            int j;
            if (i == n)
            {
                int s1, s2;
                s1 = s2 = 0;
                for (int a = 0; a < n - 1; a++)
                {
                    for (int b = a + 1; b < n; b++)
                    {
                        if (arry[a] > arry[b])
                        {
                            s1++;
                        }

                    }
                    s2 = s2 + Math.Max(0, a + 1 - arry[a]);
                }
                int count = 0;
                if (s1 == s2)
                    count++;



                return count;


            }
            else
            {
                int count = 0;
                for (j = i; j <= n; j++)
                {
                    swap(ref arry[i], ref arry[j]);
                    count += permute(arry, i + 1, n);
                    swap(ref arry[i], ref arry[j]);
                }
                return count;
            }



        }

        static void swap(ref int a, ref int b)
        {
            int tmp;
            tmp = a;
            a = b;
            b = tmp;
        }         

Answer 1

Try solving this with immutable types, its easier to reason about them. If, after solving the problem, you have a performance goal you haven't met then you can start trying to optimize the code.

Consider the following approach with an immutable stack that keeps track of the current permutation:

static IEnumerable<IEnumerable<int>> GetPermutations(IList<int> input)
{
    if (input == null)
        throw new ArgumentNullException(nameof(input));

    if (input.Count < 2)
        throw new ArgumentException("Input does not have a valid format.");

    var setSize = input[0];
    var prefixSize = input[1];

    if (prefixSize != input.Count - 2)
        throw new ArgumentException("Input does not have a valid format.");

    if (input.Skip(2).Any(i => i > setSize)) //we are assuming, per example, that valid range starts at 1.
        throw new ArgumentException("Input does not have a valid format.");

    //Ok, we've got a valid input, interesting stuff starts here.
    var prefix = input.Skip(2).ToArray();
    var initialSet = Enumerable.Range(1, setSize)
                               .Except(prefix)
                               .ToArray();

    foreach (var p in getPermutations(ImmutableStack<int>.Empty, initialSet))
    {
        yield return prefix.Concat(p);
    }

    IEnumerable<IEnumerable<int>> getPermutations(ImmutableStack<int> permutation, IEnumerable<int> set)
    {
        if (permutation.Count == setSize - prefixSize)
        {
            yield return permutation;
        }
        else
        {
            foreach (var i in set)
            {
                foreach (var p in getPermutations(permutation.Push(i), set.Except(new[] { i })))
                {
                    yield return p;
                }
            }
        }
    }
}

And that is it, solving your problem was about 10-12 lines of real code (not considering input validation). Note that I am using some c#7 features here, but its easily translatable to previous versions of the language. Also I'd like to underline the argument validation we are doing upfront; make sure you have a valid input before trying out anything.

For ImmutableStack<T> you can use the one in System.Collections.Immutable (you have to download the NuGet package) or implement your own, its simple:

private class ImmutableStack<T>: IEnumerable<T>
{
    public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>();
    private readonly T head;
    private readonly ImmutableStack<T> tail;

    private ImmutableStack() { }
    private ImmutableStack(T head, ImmutableStack<T> tail)
    {
        Debug.Assert(tail != null);
        this.head = head;
        this.tail = tail;
        Count = tail.Count + 1;
    }

    public int Count { get; }
    public T Peek() => 
        this != Empty ? head : throw new InvalidOperationException("Empty stack.");
    public ImmutableStack<T> Pop() =>
        this != Empty ? tail : throw new InvalidOperationException("Empty stack.");
    public ImmutableStack<T> Push(T item) => new ImmutableStack<T>(item, this);

    public IEnumerator<T> GetEnumerator()
    {
        var current = this;

        while (current != Empty)
        {
            yield return current.head;
            current = current.tail;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

If you use the collections in System.Collections.Immutable, then you'll probably want to use some kind of immutable set for initalSet and set.

Answer 2

You can rewrite your permute method (based on this answer):

private static IEnumerable<IEnumerable<T>> Permute<T>(List<T> prefix, List<T> suffix)
{
    for (var i = 0; i < suffix.Count; ++i)
    {
        var newPrefix = new List<T>(prefix) {suffix[i]};
        var newSuffix = new List<T>(suffix.Take(i).Concat(suffix.Skip(i + 1)));

        if (newSuffix.Count == 0)
        {
            yield return newPrefix;
            continue;
        }

        foreach (var permutation in Permute(newPrefix, newSuffix))
            yield return permutation;
    }
}

And use it like this:

public static void PrintAllPermutations()
{
    var input = new[] {5, 2, 1, 4};

    var prefix = input.Skip(2).Take(input[1]).ToList();
    var suffx = Enumerable.Range(1, input[0]).Except(prefix).ToList();

    foreach (var permutation in Permute(prefix, suffx))
        Console.WriteLine(string.Join(", ", permutation));
}

Reult would be:

1, 4, 2, 3, 5
1, 4, 2, 5, 3
1, 4, 3, 2, 5
1, 4, 3, 5, 2
1, 4, 5, 2, 3
1, 4, 5, 3, 2