列出字符串/整数的所有排列

Question

编程访谈中的一个常见任务(不是根据我的访谈经验)是采用字符串或整数并列出每个可能的排列.

有没有这样做的例子和解决这个问题背后的逻辑？

我已经看过一些代码片段,但它们没有得到很好的评论/解释,因此难以理解.

Answer 1

首先:它当然闻起来像递归!

既然你也想知道原理,我尽力解释它的人类语言.我认为大多数时候递归很容易.你只需要掌握两个步骤:

1. 第一步
2. 所有其他步骤(都具有相同的逻辑)

在人类语言中:

简而言之:
1.1个元素的排列是一个元素.
2.一组元素的排列是每个元素的列表,与其他元素的每个排列连接在一起.

例:

如果集合只有一个元素 - >
返回它.
烫发(a) - > a

如果集合有两个字符:对于其中的每个元素:返回元素,添加其余元素的排列,如下所示:

烫发(ab) - >

a +烫发(b) - > ab

b +烫发(a) - > ba

进一步:对于集合中的每个字符:返回一个字符,与该集合的其余部分的连接相连接

烫发(abc) - >

a +烫发(bc) - > abc,acb

b +烫发(ac) - > bac,bca

c + perm(ab) - > cab,cba

烫发(abc ... z) - >

a +烫发(...),b +烫发(....)
....

我在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#

好的,还有更复杂的东西(因为它被标记为c#),来自http://radio.weblogs.com/0111551/stories/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);
    }
}

Answer 2

如果允许使用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或更高版本.

Answer 3

在这里,我找到了解决方案.它是用Java编写的,但我已将其转换为C#.我希望它会对你有所帮助.

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

Answer 4

不需要递归,这里有关于此解决方案的良好信息.

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

我已经使用了这个算法多年,它有O(N) 时间和空间复杂度来计算每个排列.

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

Answer 5

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

您可以编写交换函数来交换字符.
这被称为permute(string,0);

Answer 6

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

Answer 7

首先,集合具有排列,而不是字符串或整数,所以我假设你的意思是"字符串中的字符集".

请注意,一组大小为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

Answer 8

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

Answer 9

我喜欢FBryant87方法,因为它很简单.不幸的是,它确实像许多其他"解决方案"不提供所有排列,或者如果它不止一次包含相同的数字,则提供例如整数.以656123为例.这条线:

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

使用Except将导致所有出现被删除,即当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,或者在返回后使用您喜欢的任何方法删除重复项.

Answer 10

这是一篇很好的文章,涵盖了三个用于查找所有排列的算法,包括一个用于查找下一个排列的算法.

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

C++和Python分别内置了next_permutation和itertools.permutations函数.

Answer 11

这是一个纯函数的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个以上元素的数组,int必须替换为具有更大/任意精度的类型,因为因子17会导致int32溢出.

Answer 12

这是一个易于理解的排列函数，适用于字符串和整数作为输入。有了这个，您甚至可以设置输出长度（正常情况下它等于输入长度）

细绳

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

对于Integer，只需更改调用者方法，MakePermutations()保持不变：

    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” “ad” “ba” “bc” “bd” “ca” “cb” “cd” “da” “db” “dc”

示例 3: GetAllPermutations(486,2); 48 46 84 86 64 68

Answer 13

这是c#中使用递归的简单解决方案,

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