固定接頭辞番号を持つ順列

Question

各値には別個の意味があります。最初の値は順列の長さ、2番目の値は初期接頭辞の長さ、残りの整数は1つの整数ですすべての順列の接頭辞。

配列の要素が{5,2,1,4}
の場合、5は置換配列の要素数です。 であり、2は配列順列の最初の2つの要素プレフィックスを構成する整数の長さです。 1,4は接頭辞整数、すなわち5要素置換組合せの長さ2であるので、欠落要素は2,3,5であり、1 &は以下のようにすべての置換にわたって共通の接頭辞である。
[14352] [14352] [14523] [14532]ここで、入力配列は{5,2,1,4}です
これを行うには？

私は1つの欠けている要素2,3 & 5の順列を取得するコードの下に持っていますが、私は

 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

がへの容易な、不変タイプでこれを解決してみ全体をプログラムする方法ソリューションを取得しておりません彼らについての理由。問題を解決した後で、満たしていないパフォーマンス目標がある場合は、コードの最適化を開始できます。実際のコードの約10〜12行（入力の検証を考慮していない）して、あなたの問題を解決し、

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; 
       } 
      } 
     } 
    } 
} 

そして、それはそれである：

は、現在の順列を追跡不変スタックと、次のアプローチを考えてみましょう。ここではC＃7の機能をいくつか使用していますが、以前のバージョンの言語に簡単に翻訳できます。また、私が先行している議論の検証を強調したいと思います。何か試してみる前に、正しい入力があることを確認してください。

あなたが System.Collections.Immutableに1を使用します（あなたはNuGetパッケージをダウンロードする必要が）か、独自に実装し、その簡単なことができ ImmutableStack<T>については

：

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(); 
} 

あなたはSystem.Collections.Immutableでコレクションを使用する場合、あなたはおそらくよinitalSetとsetに何らかの不変設定を使用したい

Answer 2

あなたは（このanswerに基づいて）あなたのpermuteメソッドを書き換えることができます。

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; 
    } 
} 

そして、このようにそれを使用します。

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は次のようになります。

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