سرد جميع التباديل سلسلة / عدد صحيح

https://stackoverflow.com/questions/756055

09-09-2019
|

سؤال

مهمة شائعة في مقابلات البرمجة (ليس من تجربتي في المقابلات رغم ذلك) هي أخذ سلسلة أو عدد صحيح وقوائم كل التقليب الممكن.

هل هناك مثال على كيفية القيام بذلك والمنطق وراء حل مثل هذه المشكلة؟

لقد رأيت مقتطفات برمجية قليلة لكنها لم تعلق بشكل جيد / أوضحت وبالتالي من الصعب اتباعها.

المحلول

بادئ ذي بدء: تنبعث منه رائحة العودية بالطبع بكل تأكيد!

منذ أن أردت أيضا معرفة المبدأ، بذلت قصارى جهدي لشرح ذلك اللغة البشرية. أعتقد أن العودية سهلة للغاية في معظم الأوقات. يجب عليك فقط فهم خطوتين:

الخطوة الأولى
جميع الخطوات الأخرى (كلها بنفس المنطق)

في لغة بشرية:

بالمختصر:
1. التقليب من عنصر واحد هو عنصر واحد.
2. إن التقليب من مجموعة من العناصر هو قائمة كل عنصر من العناصر، متسلسلة بكل التقابل من العناصر الأخرى.

مثال:

إذا كانت المجموعة لديها عنصر واحد فقط ->
أعده.
بيرم (أ) ->

إذا كانت المجموعة تحتوي على حرفين: لكل عنصر في ذلك: إرجاع العنصر، مع إضافة التقليب لبقية العناصر، مثل ذلك:

بيرم (AB) ->

A + PERM (B) -> واهن

ب + بيرم (أ) -> با

علاوة على ذلك: لكل حرف في المجموعة: إرجاع حرف، متسلسل مع ترتبيد> بقية المجموعة

بيرم (ABC) ->

A + Perm (BC) -> ABC., إكهرباء

ب + بيرم (AC) -> باك, bca.

ج + بيرم (AB) -> سيارة أجرة, CBA.

بيرم (ABC ... Z) ->

A + Perm (...)، B + Perm (....)
....

لقد وجدت كود مزيف على http://www.programmersheaven.com/mb/algorithms/369713/369713/permutation-algorithm-help/:

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

ج #

حسنا، وشيء أكثر تفصيلا (وبما هو الموسومة C #)، من http://radio.weblogs.com/0111551/Sories/2002/10/14/Permutations.html. : إلى حد ما، لكنني قررت نسخها على أي حال، لذلك لا يعتمد المنشور على الأصل.

تأخذ الوظيفة سلسلة من الأحرف، ويكتب كل التقليب الممكنة لهذه السلسلة الدقيقة، لذلك على سبيل المثال، إذا تم توفير "ABC"، يجب أن تسكب:

ABC، ACB، BAC، BCA، CAB، CBA.

رمز:

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

نصائح أخرى

إنه سطرين فقط من التعليمات البرمجية إذا سمح Linq باستخدامه. يرجى الاطلاع على جوابي هنا.

تعديل

هنا هي وظيفتي العامة التي يمكن أن تعيد جميع التباديلات (وليس مجموعات) من قائمة T:

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

مثال:

IEnumerable<IEnumerable<int>> result =
    GetPermutations(Enumerable.Range(1, 3), 3);

الإخراج - قائمة من القوائم الصحيحة:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

نظرا لأن هذه الوظيفة تستخدم LINQ لذلك يتطلب .NET 3.5 أو أعلى.

هنا لقد وجدت الحل. كتبت في جافا، لكنني حولتها إلى C #. آمل أن تساعدك.

Enter image description here

إليك الرمز في C #:

static void Main(string[] args)
{
    string str = "ABC";
    char[] charArry = str.ToCharArray();
    permute(charArry, 0, 2);
    Console.ReadKey();
}

static void permute(char[] arry, int i, int n)
{
    int j;
    if (i==n)
        Console.WriteLine(arry);
    else
    {
        for(j = i; j <=n; j++)
        {
            swap(ref arry[i],ref arry[j]);
            permute(arry,i+1,n);
            swap(ref arry[i], ref arry[j]); //backtrack
        }
    }
}

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

العودية ليس ضروري، هنا هي معلومات جيدة حول هذا الحل.

var values1 = new[] { 1, 2, 3, 4, 5 };

foreach (var permutation in values1.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };

foreach (var permutation in values2.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Console.ReadLine();

لقد استخدمت هذه الخوارزمية لسنوات، لديها على) زمن و الفضاء تعقيد لحساب كل التقليب.

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[]) array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

يمكنك كتابة وظيفة المبادلة الخاصة بك إلى الأحرف المبادلة.
هذا هو ما يسمى كسمادي (سلسلة، 0)؛

بادئ ذي بدء، تحتوي مجموعات على تصارات، وليس سلاسل أو أعداد صحيحة، لذلك سأفترض أنك تعني "مجموعة الأحرف في سلسلة".

لاحظ أن مجموعة من حجم N لديه ن! N- التباديل.

الدعوة الكفاءة التالية (من ويكيبيديا)، تسمى K = 1 ... N! سيعطي كل التباديلات:

function permutation(k, s) {
    for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j; // integer division cuts off the remainder
    }
    return s;
}

إليك رمز Python المكافئ (مؤشرات الصفيف المستندة إلى 0):

def permutation(k, s):
    r = s[:]
    for j in range(2, len(s)+1):
        r[j-1], r[k%j] = r[k%j], r[j-1]
        k = k/j+1
    return r

نسخة معدلة قليلا في C # أن العائدات التي تحتاج إلى التباديل في صفيف من أي نوع.

    // USAGE: create an array of any type, and call Permutations()
    var vals = new[] {"a", "bb", "ccc"};
    foreach (var v in Permutations(vals))
        Console.WriteLine(string.Join(",", v)); // Print values separated by comma


public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
    if (fromInd + 1 == values.Length)
        yield return values;
    else
    {
        foreach (var v in Permutations(values, fromInd + 1))
            yield return v;

        for (var i = fromInd + 1; i < values.Length; i++)
        {
            SwapValues(values, fromInd, i);
            foreach (var v in Permutations(values, fromInd + 1))
                yield return v;
            SwapValues(values, fromInd, i);
        }
    }
}

private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        T tmp = values[pos1];
        values[pos1] = values[pos2];
        values[pos2] = tmp;
    }
}

أحببت FBRYANT87. نهج لأنه بسيط. لسوء الحظ، فإنه مثل "الحلول" الأخرى الأخرى لا تقدم جميع التباديل أو على سبيل المثال عدد صحيح إذا كان يحتوي على نفس الرقم أكثر من مرة. خذ 656123 كمثال. الخط:

var tail = chars.Except(new List<char>(){c});

باستخدام باستثناء سيؤدي إلى إزالة جميع الأحداث، أي عند إزالته C = 6، تتم إزالة رقمين وتركنا مع 5123. نظرا لعدم أي من الحلول التي حاولت حلها، قررت أن أحاول وحلها بنفسي FBRYANT87.رمز كأداة. هذا هو ما خطرت لي:

private static List<string> FindPermutations(string set)
    {
        var output = new List<string>();
        if (set.Length == 1)
        {
            output.Add(set);
        }
        else
        {
            foreach (var c in set)
            {
                // Remove one occurrence of the char (not all)
                var tail = set.Remove(set.IndexOf(c), 1);
                foreach (var tailPerms in FindPermutations(tail))
                {
                    output.Add(c + tailPerms);
                }
            }
        }
        return output;
    }

أنا ببساطة فقط إزالة أول العثور عليها باستخدام .remove و .indexof. يبدو أن العمل كما هو مخصص لاستخدامي على الأقل. أنا متأكد من أنه يمكن أن يتم بذكاء.

شيء واحد يجب ملاحظة ذلك: قد تحتوي القائمة الناتجة على التكرارات، لذلك تأكد من أنك إما أن تجعل الطريقة إرجاعها على سبيل المثال Hashset بدلا من ذلك أو قم بإزالة التكرارات بعد الإرجاع باستخدام أي طريقة تريدها.

إليك مقالة جيدة تغطي ثلاث خوارزميات لإيجاد جميع التباديلات، بما في ذلك واحدة للعثور على التقليب التالي.

http://www.cut-the-knot.org/do_you_know/allperm.shtml.

C ++ و Python لديها مدمج next_permulation. و itertools.permutations. وظائف على التوالي.

إليك تطبيق F # وظيفي بحت:


let factorial i =
    let rec fact n x =
        match n with
        | 0 -> 1
        | 1 -> x
        | _ -> fact (n-1) (x*n)
    fact i 1

let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a array) =
    if j = (r.Length + 1) then r
    else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }

يمكن تحسين الأداء بشكل كبير عن طريق تغيير المبادلة للاستفادة من الطبيعة القابلة للتغيير من صفائف CLR، ولكن هذا التنفيذ هو مؤمن الخيط فيما يتعلق بمجموعة المصدر وقد يكون ذلك مرغوبا في بعض السياقات. أيضا، يجب استبدال المصفوفات التي تحتوي على أكثر من 16 عنصرا، أن يتم استبدالها بأنواعها ذات الدقة العظمى / التعسفي حيث أن 17 نتائج فنية في فائض Int32.

فيما يلي حلا بسيطا في C # باستخدام Recursion،

void Main()
{
    string word = "abc";
    WordPermuatation("",word);
}

void WordPermuatation(string prefix, string word)
{
    int n = word.Length;
    if (n == 0) { Console.WriteLine(prefix); }
    else
    {
        for (int i = 0; i < n; i++)
        {
            WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
        }
    }
}

هنا سهلة الفهم وظيفة الترتيب الثنائية لكل من السلسلة والأعتماء كمدخلات. مع هذا يمكنك حتى تعيين طول الإخراج الخاص بك(أي في حالة طبيعية يساوي طول الإدخال)

سلسلة

    static ICollection<string> result;

    public static ICollection<string> GetAllPermutations(string str, int outputLength)
    {
        result = new List<string>();
        MakePermutations(str.ToCharArray(), string.Empty, outputLength);
        return result;
    }

    private static void MakePermutations(
       char[] possibleArray,//all chars extracted from input
       string permutation,
       int outputLength//the length of output)
    {
         if (permutation.Length < outputLength)
         {
             for (int i = 0; i < possibleArray.Length; i++)
             {
                 var tempList = possibleArray.ToList<char>();
                 tempList.RemoveAt(i);
                 MakePermutations(tempList.ToArray(), 
                      string.Concat(permutation, possibleArray[i]), outputLength);
             }
         }
         else if (!result.Contains(permutation))
            result.Add(permutation);
    }

ولل عدد صحيح فقط قم بتغيير طريقة المتصل و تكسير () لا يزال لم يمس:

    public static ICollection<int> GetAllPermutations(int input, int outputLength)
    {
        result = new List<string>();
        MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
        return result.Select(m => int.Parse(m)).ToList<int>();
    }

مثال 1: getallpermutations ("ABC"، 3)؛ "ABC" "ACB" "BAC" "BCA" "CAB" "CBA"

مثال 2: Getallpermutations ("ABCD"، 2)؛ "AB" "AC" "إعلان" "BA" "BA" "BD" "CA" "CB" "CD" "DB" "DC"

مثال 3: getallpermutations (486،2)؛ 48 46 84 86 64 68

class Program
{
    public static void Main(string[] args)
    {
        Permutation("abc");
    }

    static void Permutation(string rest, string prefix = "")
    {
        if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);

        // Each letter has a chance to be permutated
        for (int i = 0; i < rest.Length; i++)
        {                
            Permutation(rest.Remove(i, 1), prefix + rest[i]);
        }
    }
}

هنا هي الوظيفة التي سطبع جميع برمجية. هذه الوظائف تنفذ منطق شرح من قبل بيتر.

public class Permutation
{
    //http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm

    public static void permuteString(String beginningString, String endingString)
    {           

        if (endingString.Length <= 1)
            Console.WriteLine(beginningString + endingString);
        else
            for (int i = 0; i < endingString.Length; i++)
            {

                String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);

                permuteString(beginningString + endingString.ElementAt(i), newString);

            }
    }
}

    static void Main(string[] args)
    {

        Permutation.permuteString(String.Empty, "abc");
        Console.ReadLine();

    }

أدناه هو تنفيذ التقليب. لا تمانع في الأسماء المتغيرة، كما كنت أفعل ذلك للمتعة :)

class combinations
{
    static void Main()
    {

        string choice = "y";
        do
        {
            try
            {
                Console.WriteLine("Enter word :");
                string abc = Console.ReadLine().ToString();
                Console.WriteLine("Combinatins for word :");
                List<string> final = comb(abc);
                int count = 1;
                foreach (string s in final)
                {
                    Console.WriteLine("{0} --> {1}", count++, s);
                }
                Console.WriteLine("Do you wish to continue(y/n)?");
                choice = Console.ReadLine().ToString();
            }
            catch (Exception exc)
            {
                Console.WriteLine(exc);
            }
        } while (choice == "y" || choice == "Y");
    }

    static string swap(string test)
    {
        return swap(0, 1, test);
    }

    static List<string> comb(string test)
    {
        List<string> sec = new List<string>();
        List<string> first = new List<string>();
        if (test.Length == 1) first.Add(test);
        else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
        else if (test.Length > 2)
        {
            sec = generateWords(test);
            foreach (string s in sec)
            {
                string init = s.Substring(0, 1);
                string restOfbody = s.Substring(1, s.Length - 1);

                List<string> third = comb(restOfbody);
                foreach (string s1 in third)
                {
                    if (!first.Contains(init + s1)) first.Add(init + s1);
                }


            }
        }

        return first;
    }

    static string ShiftBack(string abc)
    {
        char[] arr = abc.ToCharArray();
        char temp = arr[0];
        string wrd = string.Empty;
        for (int i = 1; i < arr.Length; i++)
        {
            wrd += arr[i];
        }

        wrd += temp;
        return wrd;
    }

    static List<string> generateWords(string test)
    {
        List<string> final = new List<string>();
        if (test.Length == 1)
            final.Add(test);
        else
        {
            final.Add(test);
            string holdString = test;
            while (final.Count < test.Length)
            {
                holdString = ShiftBack(holdString);
                final.Add(holdString);
            }
        }

        return final;
    }

    static string swap(int currentPosition, int targetPosition, string temp)
    {
        char[] arr = temp.ToCharArray();
        char t = arr[currentPosition];
        arr[currentPosition] = arr[targetPosition];
        arr[targetPosition] = t;
        string word = string.Empty;
        for (int i = 0; i < arr.Length; i++)
        {
            word += arr[i];

        }

        return word;

    }
}

إليك مثال رفيع المستوى كتبت والتي توضح لغة بشرية Explanation Peter أعطى:

    public List<string> FindPermutations(string input)
    {
        if (input.Length == 1)
            return new List<string> { input };
        var perms = new List<string>();
        foreach (var c in input)
        {
            var others = input.Remove(input.IndexOf(c), 1);
            perms.AddRange(FindPermutations(others).Select(perm => c + perm));
        }
        return perms;
    }

إذا كانت الأداء والذاكرة مشكلة، أقترح هذا التنفيذ فعال للغاية. وفق خوارزمية كومة في ويكيبيديا, ، يجب أن يكون الأسرع. آمل أن يناسب احتياجك :-)!

تماما كمقارنة من هذا مع تنفيذ LINQ لمدة 10! (التعليمات البرمجية المدرجة):

هذا: 36288000 عناصر في 235 مللي ثانية

LINQ: 36288000 عناصر في 50051 ملليزيك

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;

namespace WpfPermutations
{
    /// <summary>
    /// EO: 2016-04-14
    /// Generator of all permutations of an array of anything.
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// </summary>
    public static class Permutations
    {
        /// <summary>
        /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
        /// </summary>
        /// <param name="items">Items to permute in each possible ways</param>
        /// <param name="funcExecuteAndTellIfShouldStop"></param>
        /// <returns>Return true if cancelled</returns> 
        public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
        {
            int countOfItem = items.Length;

            if (countOfItem <= 1)
            {
                return funcExecuteAndTellIfShouldStop(items);
            }

            var indexes = new int[countOfItem];
            for (int i = 0; i < countOfItem; i++)
            {
                indexes[i] = 0;
            }

            if (funcExecuteAndTellIfShouldStop(items))
            {
                return true;
            }

            for (int i = 1; i < countOfItem;)
            {
                if (indexes[i] < i)
                { // On the web there is an implementation with a multiplication which should be less efficient.
                    if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                    {
                        Swap(ref items[i], ref items[indexes[i]]);
                    }
                    else
                    {
                        Swap(ref items[i], ref items[0]);
                    }

                    if (funcExecuteAndTellIfShouldStop(items))
                    {
                        return true;
                    }

                    indexes[i]++;
                    i = 1;
                }
                else
                {
                    indexes[i++] = 0;
                }
            }

            return false;
        }

        /// <summary>
        /// This function is to show a linq way but is far less efficient
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });

            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

        /// <summary>
        /// Swap 2 elements of same type
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <param name="b"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            T temp = a;
            a = b;
            b = temp;
        }

        /// <summary>
        /// Func to show how to call. It does a little test for an array of 4 items.
        /// </summary>
        public static void Test()
        {
            ForAllPermutation("123".ToCharArray(), (vals) =>
            {
                Debug.Print(String.Join("", vals));
                return false;
            });

            int[] values = new int[] { 0, 1, 2, 4 };

            Debug.Print("Non Linq");
            ForAllPermutation(values, (vals) =>
            {
                Debug.Print(String.Join("", vals));
                return false;
            });

            Debug.Print("Linq");
            foreach(var v in GetPermutations(values, values.Length))
            {
                Debug.Print(String.Join("", v));
            }

            // Performance
            int count = 0;

            values = new int[10];
            for(int n = 0; n < values.Length; n++)
            {
                values[n] = n;
            }

            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Reset();
            stopWatch.Start();

            ForAllPermutation(values, (vals) =>
            {
                foreach(var v in vals)
                {
                    count++;
                }
                return false;
            });

            stopWatch.Stop();
            Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");

            count = 0;
            stopWatch.Reset();
            stopWatch.Start();

            foreach (var vals in GetPermutations(values, values.Length))
            {
                foreach (var v in vals)
                {
                    count++;
                }
            }

            stopWatch.Stop();
            Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");

        }
    }
}

إليك حلاي في جافا سكريبت (nodejs). الفكرة الرئيسية هي أننا نأخذ عنصرا واحدا في وقت واحد، "إزالته" من السلسلة، وتغيير بقية الأحرف، وأدخل العنصر في المقدمة.

function perms (string) {
  if (string.length == 0) {
    return [];
  }
  if (string.length == 1) {
    return [string];
  }
  var list = [];
  for(var i = 0; i < string.length; i++) {
    var invariant = string[i];
    var rest = string.substr(0, i) + string.substr(i + 1);
    var newPerms = perms(rest);
    for (var j = 0; j < newPerms.length; j++) {
      list.push(invariant + newPerms[j]);
    }
  }
  return list;
}

module.exports = perms;

وهنا الاختبارات:

require('should');
var permutations = require('../src/perms');

describe('permutations', function () {
  it('should permute ""', function () {
    permutations('').should.eql([]);
  })

  it('should permute "1"', function () {
    permutations('1').should.eql(['1']);
  })

  it('should permute "12"', function () {
    permutations('12').should.eql(['12', '21']);
  })

  it('should permute "123"', function () {
    var expected = ['123', '132', '321', '213', '231', '312'];
    var actual = permutations('123');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })

  it('should permute "1234"', function () {
    // Wolfram Alpha FTW!
    var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
    var actual = permutations('1234');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })
})

هنا هو أبسط الحل الذي يمكنني التفكير فيه:

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs

ال distribute وظيفة تأخذ عنصر جديد e و nالقائمة القائمة وإرجاع قائمة n+1 يسرد كل منها لديه e إدراج في مكان مختلف. على سبيل المثال، إدراج 10 في كل من الأماكن الأربعة الممكنة في القائمة [1;2;3]:

> distribute 10 [1..3];;
val it : int list list =
  [[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]

ال permute تعمل الوظيفة على طيات كل عنصر بدوره توزيع البراءات المتراكمة حتى الآن، على ذروتها في جميع التباديل. على سبيل المثال، 6 التباديلات القائمة [1;2;3]:

> permute [1;2;3];;
val it : int list list =
  [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]

تغيير fold إلى أ scan من أجل الحفاظ على المتراكم المتوسطين يلقيون بعض الضوء حول كيفية إنشاء التباديل عنصر في وقت واحد:

> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
  seq
    [[[]]; [[1]]; [[2; 1]; [1; 2]];
     [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]

يسرد التباديل لسلسلة. يتجنب الازدواجية عندما تتكرر الأحرف:

using System;
using System.Collections;

class Permutation{
  static IEnumerable Permutations(string word){
    if (word == null || word.Length <= 1) {
      yield return word;
      yield break;
    }

    char firstChar = word[0];
    foreach( string subPermute in Permutations (word.Substring (1)) ) {
      int indexOfFirstChar = subPermute.IndexOf (firstChar);
      if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;

      for( int index = 0; index <= indexOfFirstChar; index++ )
        yield return subPermute.Insert (index, new string (firstChar, 1));
    }
  }

  static void Main(){
    foreach( var permutation in Permutations ("aab") )
      Console.WriteLine (permutation);
  }
}

هنا هي الوظيفة التي سطبع جميع التباديل بشكل متكرر.

public void Permutations(string input, StringBuilder sb)
    {
        if (sb.Length == input.Length)
        {
            Console.WriteLine(sb.ToString());
            return;
        }

        char[] inChar = input.ToCharArray();

        for (int i = 0; i < input.Length; i++)
        {
            if (!sb.ToString().Contains(inChar[i]))
            {
                sb.Append(inChar[i]);
                Permutations(input, sb);    
                RemoveChar(sb, inChar[i]);
            }
        }
    }

private bool RemoveChar(StringBuilder input, char toRemove)
    {
        int index = input.ToString().IndexOf(toRemove);
        if (index >= 0)
        {
            input.Remove(index, 1);
            return true;
        }
        return false;
    }

class Permutation
{
    public static List<string> Permutate(string seed, List<string> lstsList)
    {
        loopCounter = 0;
        // string s="\w{0,2}";
        var lstStrs = PermuateRecursive(seed);

        Trace.WriteLine("Loop counter :" + loopCounter);
        return lstStrs;
    }

    // Recursive function to find permutation
    private static List<string> PermuateRecursive(string seed)
    {
        List<string> lstStrs = new List<string>();

        if (seed.Length > 2)
        {
            for (int i = 0; i < seed.Length; i++)
            {
                str = Swap(seed, 0, i);

                PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
                    s =>
                    {
                        lstStrs.Add(str[0] + s);
                        loopCounter++;
                    });
                ;
            }
        }
        else
        {
            lstStrs.Add(seed);
            lstStrs.Add(Swap(seed, 0, 1));
        }
        return lstStrs;
    }
    //Loop counter variable to count total number of loop execution in various functions
    private static int loopCounter = 0;

    //Non recursive  version of permuation function
    public static List<string> Permutate(string seed)
    {
        loopCounter = 0;
        List<string> strList = new List<string>();
        strList.Add(seed);
        for (int i = 0; i < seed.Length; i++)
        {
            int count = strList.Count;
            for (int j = i + 1; j < seed.Length; j++)
            {
                for (int k = 0; k < count; k++)
                {
                    strList.Add(Swap(strList[k], i, j));
                    loopCounter++;
                }
            }
        }
        Trace.WriteLine("Loop counter :" + loopCounter);
        return strList;
    }

    private static string Swap(string seed, int p, int p2)
    {
        Char[] chars = seed.ToCharArray();
        char temp = chars[p2];
        chars[p2] = chars[p];
        chars[p] = temp;
        return new string(chars);
    }
}

هنا إجابة C # التي هي مبسطة قليلا.

public static void StringPermutationsDemo()
{
    strBldr = new StringBuilder();

    string result = Permute("ABCD".ToCharArray(), 0);
    MessageBox.Show(result);
}     

static string Permute(char[] elementsList, int startIndex)
{
    if (startIndex == elementsList.Length)
    {
        foreach (char element in elementsList)
        {
            strBldr.Append(" " + element);
        }
        strBldr.AppendLine("");
    }
    else
    {
        for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
        {
            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);

            Permute(elementsList, (startIndex + 1));

            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
        }
    }

    return strBldr.ToString();
}

static void Swap(ref char Char1, ref char Char2)
{
    char tempElement = Char1;
    Char1 = Char2;
    Char2 = tempElement;
}

انتاج:

هذا هو الحل الذي يسهل علي أن أفهمه

class ClassicPermutationProblem
{
    ClassicPermutationProblem() { }

    private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
    {
         foreach (T element in list)
         {
             List<T> currentTemp = temp.ToList();
             if (!currentTemp.Contains(element))
                currentTemp.Add(element);
             else
                continue;

             if (position == list.Count)
                finalList.Add(currentTemp);
             else
                PopulatePosition(finalList, list, currentTemp, position + 1);
        }
    }

    public static List<List<int>> GetPermutations(List<int> list)
    {
        List<List<int>> results = new List<List<int>>();
        PopulatePosition(results, list, new List<int>(), 1);
        return results;
     }
}

static void Main(string[] args)
{
    List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}

هنا هو واحد آخر تنفيذ Algo المذكورة.

public class Program
{
    public static void Main(string[] args)
    {
        string str = "abcefgh";
        var astr = new Permutation().GenerateFor(str);
        Console.WriteLine(astr.Length);
        foreach(var a in astr)
        {
            Console.WriteLine(a);
        }
        //a.ForEach(Console.WriteLine);
    }
}

class Permutation
{
    public string[] GenerateFor(string s)
    {  

        if(s.Length == 1)
        {

            return new []{s}; 
        }

        else if(s.Length == 2)
        {

            return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};

        }

        var comb = new List<string>();

        foreach(var c in s)
        {

            string cStr = c.ToString();

            var sToProcess = s.Replace(cStr,"");
            if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
            {
                var conCatStr = GenerateFor(sToProcess);



                foreach(var a in conCatStr)
                {
                    comb.Add(c.ToString()+a);
                }


            }
        }
        return comb.ToArray();

    }
}

    //Generic C# Method
            private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
            {
                var perms = new List<T[]>();

                var l = input.Length - 1;

                if (l == startIndex)
                    perms.Add(input);
                else
                {

                    for (int i = startIndex; i <= l; i++)
                    {
                        var copy = input.ToArray(); //make copy

                        var temp = copy[startIndex];

                        copy[startIndex] = copy[i];
                        copy[i] = temp;

                        perms.AddRange(GetPerms(copy, startIndex + 1));

                    }
                }

                return perms;
            }

            //usages
            char[] charArray = new char[] { 'A', 'B', 'C' };
            var charPerms = GetPerms(charArray);


            string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
            var stringPerms = GetPerms(stringArray);


            int[] intArray = new int[] { 1, 2, 3 };
            var intPerms = GetPerms(intArray);

    /// <summary>
    /// Print All the Permutations.
    /// </summary>
    /// <param name="inputStr">input string</param>
    /// <param name="strLength">length of the string</param>
    /// <param name="outputStr">output string</param>
    private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars)
    {
        //Means you have completed a permutation.
        if (outputStr.Length == NumberOfChars)
        {
            Console.WriteLine(outputStr);                
            return;
        }

        //For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc.
        for(int i=0 ; i< strLength; i++)
        {
            // Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc.
            PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4);
        }
    }

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow