75

次のように、セット (コレクション) のすべての順列を生成したいと思います。

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

一般に、これは「どのように」という問題ではなく、どのように最も効率的に行うかという問題です。また、すべての順列を生成してそれらを返すのではなく、一度に 1 つの順列のみを生成し、必要な場合にのみ続行します (イテレーターのように-私も試しましたが、少ないことが判明しました)効率的)。

私は多くのアルゴリズムとアプローチをテストし、このコードを思いつきました。これは、私が試したものの中で最も効率的です。

public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
    // More efficient to have a variable instead of accessing a property
    var count = elements.Length;

    // Indicates whether this is the last lexicographic permutation
    var done = true;

    // Go through the array from last to first
    for (var i = count - 1; i > 0; i--)
    {
        var curr = elements[i];

        // Check if the current element is less than the one before it
        if (curr.CompareTo(elements[i - 1]) < 0)
        {
            continue;
        }

        // An element bigger than the one before it has been found,
        // so this isn't the last lexicographic permutation.
        done = false;

        // Save the previous (bigger) element in a variable for more efficiency.
        var prev = elements[i - 1];

        // Have a variable to hold the index of the element to swap
        // with the previous element (the to-swap element would be
        // the smallest element that comes after the previous element
        // and is bigger than the previous element), initializing it
        // as the current index of the current item (curr).
        var currIndex = i;

        // Go through the array from the element after the current one to last
        for (var j = i + 1; j < count; j++)
        {
            // Save into variable for more efficiency
            var tmp = elements[j];

            // Check if tmp suits the "next swap" conditions:
            // Smallest, but bigger than the "prev" element
            if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
            {
                curr = tmp;
                currIndex = j;
            }
        }

        // Swap the "prev" with the new "curr" (the swap-with element)
        elements[currIndex] = prev;
        elements[i - 1] = curr;

        // Reverse the order of the tail, in order to reset it's lexicographic order
        for (var j = count - 1; j > i; j--, i++)
        {
            var tmp = elements[j];
            elements[j] = elements[i];
            elements[i] = tmp;
        }

        // Break since we have got the next permutation
        // The reason to have all the logic inside the loop is
        // to prevent the need of an extra variable indicating "i" when
        // the next needed swap is found (moving "i" outside the loop is a
        // bad practice, and isn't very readable, so I preferred not doing
        // that as well).
        break;
    }

    // Return whether this has been the last lexicographic permutation.
    return done;
}

使用法は、要素の配列を送信し、これが最後の辞書順列であるかどうかを示すブール値を取得し、配列を次の順列に変更することです。

使用例:

var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
    PrintArray(arr);
}

問題は、コードの速度に満足していないことです。

サイズ 11 の配列のすべての順列を反復処理するには、約 4 秒かかります。サイズ 11 のセットの可能な順列の量は11!4000 万近くあるため、印象的と見なすこともできます。

論理的には、サイズ 12 の配列では、 12!isであるため、約 12 倍の時間11! * 12がかかり、サイズ 13 の配列では、サイズ 12 でかかった時間の約 13 倍の時間がかかります。

したがって、サイズが 12 以上の配列では、すべての順列を処理するのに非常に長い時間がかかることが容易に理解できます。

そして、どうにかしてその時間を大幅に削減できるという強い予感があります (C# 以外の言語に切り替えることなく - コンパイラの最適化は実際にはかなりうまく最適化され、Assembly で手動で適切に最適化できるとは思えないからです)。

それをより速く行うための他の方法を知っている人はいますか?現在のアルゴリズムを高速化する方法について何か考えはありますか?

そのために外部ライブラリやサービスを使用したくないことに注意してください-コード自体が必要であり、人間が可能な限り効率的であることを望んでいます。

4

18 に答える 18

38

これはあなたが探しているものかもしれません。

    private static bool NextPermutation(int[] numList)
    {
        /*
         Knuths
         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
         2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
         3. Swap a[j] with a[l].
         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

         */
        var largestIndex = -1;
        for (var i = numList.Length - 2; i >= 0; i--)
        {
            if (numList[i] < numList[i + 1]) {
                largestIndex = i;
                break;
            }
        }

        if (largestIndex < 0) return false;

        var largestIndex2 = -1;
        for (var i = numList.Length - 1 ; i >= 0; i--) {
            if (numList[largestIndex] < numList[i]) {
                largestIndex2 = i;
                break;
            }
        }

        var tmp = numList[largestIndex];
        numList[largestIndex] = numList[largestIndex2];
        numList[largestIndex2] = tmp;

        for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {
            tmp = numList[i];
            numList[i] = numList[j];
            numList[j] = tmp;
        }

        return true;
    }
于 2012-06-26T13:37:04.030 に答える
12

それを C で処理してから、選択した言語に翻訳できる場合は、これよりもはるかに速く進むことはできません。時間が支配されるためprintです。

void perm(char* s, int n, int i){
  if (i >= n-1) print(s);
  else {
    perm(s, n, i+1);
    for (int j = i+1; j<n; j++){
      swap(s[i], s[j]);
      perm(s, n, i+1);
      swap(s[i], s[j]);
    }
  }
}

perm("ABC", 3, 0);
于 2012-06-26T18:23:53.190 に答える
8

私が知っている最速の順列アルゴリズムは、QuickPerm アルゴリズムです。
これが実装です。これはyield returnを使用しているため、必要に応じて一度に1つずつ反復できます。

コード:

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        List<T> list = new List<T>(set);

        int i, j, tmp; // Upper Index i; Lower Index j

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

                for (int x = 0; x < N; x++)
                {
                    yieldRet[x] = list[a[x]-1];
                }
                yield return yieldRet;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }
于 2012-06-26T13:49:24.013 に答える
4

これが私が最終的に最速の実装です:

public class Permutations
{
    private readonly Mutex _mutex = new Mutex();

    private Action<int[]> _action;
    private Action<IntPtr> _actionUnsafe;
    private unsafe int* _arr;
    private IntPtr _arrIntPtr;
    private unsafe int* _last;
    private unsafe int* _lastPrev;
    private unsafe int* _lastPrevPrev;

    public int Size { get; private set; }

    public bool IsRunning()
    {
        return this._mutex.SafeWaitHandle.IsClosed;
    }

    public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
    {
        return this.Permutate(start, count, action, null, async);
    }

    public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
    {
        return this.Permutate(start, count, null, actionUnsafe, async);
    }

    private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
    {
        if (!this._mutex.WaitOne(0))
        {
            return false;
        }

        var x = (Action)(() =>
                             {
                                 this._actionUnsafe = actionUnsafe;
                                 this._action = action;

                                 this.Size = count;

                                 this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
                                 this._arrIntPtr = new IntPtr(this._arr);

                                 for (var i = 0; i < count - 3; i++)
                                 {
                                     this._arr[i] = start + i;
                                 }

                                 this._last = this._arr + count - 1;
                                 this._lastPrev = this._last - 1;
                                 this._lastPrevPrev = this._lastPrev - 1;

                                 *this._last = count - 1;
                                 *this._lastPrev = count - 2;
                                 *this._lastPrevPrev = count - 3;

                                 this.Permutate(count, this._arr);
                             });

        if (!async)
        {
            x();
        }
        else
        {
            new Thread(() => x()).Start();
        }

        return true;
    }

    private unsafe void Permutate(int size, int* start)
    {
        if (size == 3)
        {
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();

            return;
        }

        var sizeDec = size - 1;
        var startNext = start + 1;
        var usedStarters = 0;

        for (var i = 0; i < sizeDec; i++)
        {
            this.Permutate(sizeDec, startNext);

            usedStarters |= 1 << *start;

            for (var j = startNext; j <= this._last; j++)
            {
                var mask = 1 << *j;

                if ((usedStarters & mask) != mask)
                {
                    Swap(start, j);
                    break;
                }
            }
        }

        this.Permutate(sizeDec, startNext);

        if (size == this.Size)
        {
            this._mutex.ReleaseMutex();
        }
    }

    private unsafe void DoAction()
    {
        if (this._action == null)
        {
            if (this._actionUnsafe != null)
            {
                this._actionUnsafe(this._arrIntPtr);
            }

            return;
        }

        var result = new int[this.Size];

        fixed (int* pt = result)
        {
            var limit = pt + this.Size;
            var resultPtr = pt;
            var arrayPtr = this._arr;

            while (resultPtr < limit)
            {
                *resultPtr = *arrayPtr;
                resultPtr++;
                arrayPtr++;
            }
        }

        this._action(result);
    }

    private static unsafe void Swap(int* a, int* b)
    {
        var tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

使用法とテストのパフォーマンス:

var perms = new Permutations();

var sw1 = Stopwatch.StartNew();

perms.Permutate(0,
                11,
                (Action<int[]>)null); // Comment this line and...
                //PrintArr); // Uncomment this line, to print permutations

sw1.Stop();
Console.WriteLine(sw1.Elapsed);

印刷方法:

private static void PrintArr(int[] arr)
{
    Console.WriteLine(string.Join(",", arr));
}

さらに詳しく:

私はこれについて非常に長い間考えていなかったので、コードを説明することしかできませんが、一般的な考え方は次のとおりです。

  1. 順列は辞書式ではありません。これにより、順列間で実際に実行する操作が少なくなります。
  2. 実装は再帰的であり、「ビュー」サイズが 3 の場合、複雑なロジックをスキップし、6 つのスワップを実行して 6 つの順列 (または必要に応じてサブ順列) を取得します。
  3. 順列は辞書式の順序ではないため、現在の「ビュー」(サブ順列) の先頭にどの要素を持ち込むかをどのように決定できますか? 現在のサブ置換再帰呼び出しで「スターター」として既に使用されている要素の記録を保持し、配列の末尾で使用されていない要素を単純に直線的に検索します。
  4. 実装は整数のみを対象としているため、要素の汎用コレクションを並べ替えるには、実際のコレクションの代わりに Permutations クラスを使用してインデックスを並べ替えるだけです。
  5. Mutex は、実行が非同期の場合に問題が発生しないようにするためのものです (順列配列へのポインターを取得する UnsafeAction パラメーターを渡すことができることに注意してください。その配列内の要素の順序を変更してはなりません)。 (ポインター)! 必要に応じて、配列を tmp 配列にコピーするか、それを処理するセーフ アクション パラメーターを使用する必要があります (渡された配列は既にコピーです)。

ノート:

この実装が実際にどれほど優れているかはわかりません。長い間触れていません。自分でテストして他の実装と比較し、フィードバックがあればお知らせください。

楽しみ。

于 2014-07-20T15:34:21.253 に答える
3

これは、コレクションのすべての順列を繰り返し処理し、評価関数を呼び出す汎用順列ファインダーです。評価関数が true を返した (探していた答えが見つかった) 場合、順列ファインダーは処理を停止します。

public class PermutationFinder<T>
{
    private T[] items;
    private Predicate<T[]> SuccessFunc;
    private bool success = false;
    private int itemsCount;

    public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
    {
        this.items = items;
        this.SuccessFunc = SuccessFunc;
        this.itemsCount = items.Count();

        Recurse(0);
    }

    private void Recurse(int index)
    {
        T tmp;

        if (index == itemsCount)
            success = SuccessFunc(items);
        else
        {
            for (int i = index; i < itemsCount; i++)
            {
                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;

                Recurse(index + 1);

                if (success)
                    break;

                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;
            }
        }
    }
}

簡単な実装を次に示します。

class Program
{
    static void Main(string[] args)
    {
        new Program().Start();
    }

    void Start()
    {
        string[] items = new string[5];
        items[0] = "A";
        items[1] = "B";
        items[2] = "C";
        items[3] = "D";
        items[4] = "E";
        new PermutationFinder<string>().Evaluate(items, Evaluate);
        Console.ReadLine();
    }

    public bool Evaluate(string[] items)
    {
        Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
        bool someCondition = false;

        if (someCondition)
            return true;  // Tell the permutation finder to stop.

        return false;
    }
}
于 2013-06-17T19:00:23.413 に答える
1

本当に桁違いの改善が見られるとしたら、私は驚かれることでしょう。あるとすれば、C# には根本的な改善が必要です。さらに、順列で何か面白いことをすると、通常、順列を生成するよりも多くの作業が必要になります。したがって、生成のコストは、物事の全体的なスキームでは重要ではありません.

とはいえ、次のことを試してみることをお勧めします。イテレータはすでに試しました。しかし、クロージャを入力として取り、見つかった順列ごとにそのクロージャを呼び出す関数を試してみましたか? C# の内部機構によっては、これがより高速になる場合があります。

同様に、特定の順列を反復処理するクロージャーを返す関数を試してみましたか?

どちらのアプローチでも、実験できるマイクロ最適化がいくつかあります。たとえば、入力配列をソートすると、その順序が常にわかります。たとえば、その要素が次の要素よりも小さいかどうかを示すブール値の配列を持つことができ、比較を行うのではなく、その配列を見てください。

于 2012-06-26T14:56:47.563 に答える
1

Knuth のものよりわずかに速いアルゴリズムを作成しました。

11 要素:

私の:0.39秒

クヌース: 0.624 秒

13 要素:

私の:56.615秒

クヌース: 98.681 秒

Javaでの私のコードは次のとおりです。

public static void main(String[] args)
{
    int n=11;
    int a,b,c,i,tmp;
    int end=(int)Math.floor(n/2);
    int[][] pos = new int[end+1][2];
    int[] perm = new int[n];

    for(i=0;i<n;i++) perm[i]=i;

    while(true)
    {
        //this is where you can use the permutations (perm)
        i=0;
        c=n;

        while(pos[i][1]==c-2 && pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]=0;
            i++;
            c-=2;
        }

        if(i==end) System.exit(0);

        a=(pos[i][0]+1)%c+i;
        b=pos[i][0]+i;

        tmp=perm[b];
        perm[b]=perm[a];
        perm[a]=tmp;

        if(pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]++;
        }
        else
        {
            pos[i][0]++;
        }
    }
}

問題は、私のアルゴリズムが奇数の要素に対してのみ機能することです。私はこのコードをすばやく書いたので、私のアイデアを実装してパフォーマンスを向上させるためのより良い方法があると確信していますが、最適化して問題を解決するために今すぐ作業する時間はありません。要素は偶数です。

これは順列ごとに 1 つのスワップであり、どの要素をスワップするかを知るために非常に単純な方法を使用します。

コードの背後にあるメソッドの説明をブログに書きました: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

于 2015-01-27T03:28:17.677 に答える
1

この質問の作成者がアルゴリズムについて尋ねていたので:

[...] 一度に 1 つの順列を生成し、必要な場合にのみ続行する

Steinhaus–Johnson–Trotter アルゴリズムを検討することをお勧めします。

Wikipedia の Steinhaus–Johnson–Trotter アルゴリズム

ここで美しく説明されています

于 2017-01-03T13:37:18.317 に答える
1

Steven Skiena のAlgorithm Design Manual (第 2 版の第 14.4 章) には、アルゴリズムの紹介と実装の概要がアクセスしやすくなっています。

Skiena は D. Knuth に言及しています。The Art of Computer Programming, Volume 4 Fascicle 2: Generating All Tuples and Permutations. アディソン・ウェズリー、2005年。

于 2012-06-26T14:11:52.963 に答える
0

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * http://marknelson.us/2002/03/01/next-permutation/
 * Rearranges the elements into the lexicographically next greater permutation and returns true.
 * When there are no more greater permutations left, the function eventually returns false.
 */

// next lexicographical permutation

template <typename T>
bool next_permutation(T &arr[], int firstIndex, int lastIndex)
{
    int i = lastIndex;
    while (i > firstIndex)
    {
        int ii = i--;
        T curr = arr[i];
        if (curr < arr[ii])
        {
            int j = lastIndex;
            while (arr[j] <= curr) j--;
            Swap(arr[i], arr[j]);
            while (ii < lastIndex)
                Swap(arr[ii++], arr[lastIndex--]);
            return true;
        }
    }
    return false;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * Swaps two variables or two array elements.
 * using references/pointers to speed up swapping.
 */
template<typename T>
void Swap(T &var1, T &var2)
{
    T temp;
    temp = var1;
    var1 = var2;
    var2 = temp;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above function
#define N 3

void OnStart()
{
    int i, x[N];
    for (i = 0; i < N; i++) x[i] = i + 1;

    printf("The %i! possible permutations with %i elements:", N, N);

    do
    {
        printf("%s", ArrayToString(x));

    } while (next_permutation(x, 0, N - 1));

}

// Output:
// The 3! possible permutations with 3 elements:
// "1,2,3"
// "1,3,2"
// "2,1,3"
// "2,3,1"
// "3,1,2"
// "3,2,1"

于 2018-02-24T02:08:45.730 に答える
0

午前 1 時、テレビを見ていたときに同じ質問を考えましたが、値は文字列でした。

単語を指定して、すべての順列を見つけます。これを簡単に変更して、配列やセットなどを処理できます。

それを解決するのに少し時間がかかりましたが、私が思いついた解決策はこれでした:

string word = "abcd";

List<string> combinations = new List<string>();

for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));
        }
    }
}

これは上記と同じコードですが、いくつかのコメントがあります

string word = "abcd";

List<string> combinations = new List<string>();

//i is the first letter of the new word combination
for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        //add the first letter of the word, j is past i so we can get all the letters from j to the end
        //then add all the letters from the front to i, then skip over i (since we already added that as the beginning of the word)
        //and get the remaining letters from i+1 to right before j.
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            //if we're at the very last word no need to get the letters after i
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            //add i as the first letter of the word, then get all the letters up to i, skip i, and then add all the lettes after i
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));

        }
    }
}
于 2017-01-24T09:54:08.953 に答える
-2

可能な順列の数を計算したいだけの場合は、上記の面倒な作業をすべて回避して、次のようなものを使用できます (c# で作成):

public static class ContrivedUtils 
{
    public static Int64 Permutations(char[] array)
    {
        if (null == array || array.Length == 0) return 0;

        Int64 permutations = array.Length;

        for (var pos = permutations; pos > 1; pos--)
            permutations *= pos - 1;

        return permutations;
    }
}

次のように呼び出します。

var permutations = ContrivedUtils.Permutations("1234".ToCharArray());
// output is: 24
var permutations = ContrivedUtils.Permutations("123456789".ToCharArray());
// output is: 362880
于 2015-02-05T18:57:06.370 に答える
-2

スワップによる単純な C# 再帰ソリューション。最初の呼び出しでは、インデックスは 0 でなければなりません

    static public void Permute<T>(List<T> input, List<List<T>> permutations, int index)
    {
        if (index == input.Count - 1)
        {
            permutations.Add(new List<T>(input));
            return;
        }

        Permute(input, permutations, index + 1);

        for (int i = index+1 ; i < input.Count; i++)
        {
            //swap
            T temp = input[index];
            input[index] = input[i];
            input[i] = temp;

            Permute(input, permutations, index + 1);

            //swap back
            temp = input[index];
            input[index] = input[i];
            input[i] = temp;
        }
    }
于 2020-09-25T15:02:02.363 に答える