logo标签列表

生成列表所有可能排列的算法是什么？

algorithmlistpermutation
128
假设我有一个包含n个元素的列表，我知道有n!种可能的方式来排列这些元素。如何生成此列表所有可能的排列？例如，我有列表[a, b, c]。该算法将返回[[a, b, c]，[a, c, b]，[b, a, c]，[b, c, a]，[c, a, b]，[c, b, a]]。
我正在阅读这里：http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations，但维基百科从来没有擅长解释，我不太理解其中的大部分内容。
答案：可以使用递归算法来生成列表的所有排列。首先，选择一个元素作为第一个元素，并将其与列表中的其他元素交换。然后，对剩余的元素进行递归处理，直到只剩下一个元素时，生成一种排列。重复此过程，每次选择一个新的第一个元素。最终，将得到所有可能的排列组合。
5
我曾经在回答另一个问题时，详细讲解了如何生成排列。我认为您会感兴趣：https://dev59.com/-HI_5IYBdhLWcg3wJfgM#1506337 - Joren
2
这可以解决你的问题：http://en.wikipedia.org/wiki/Heap's_algorithm - Felix
我写了一篇博客文章，解释了如何生成几种不同类型的组合函数。https://www.axiomtutor.com/new-blog/2022/8/3/combinatorics-simulated-in-python-using-sympy - Addem
36个回答
1
在下面的Java解决方案中，我们利用字符串是不可变的这一事实，以避免在每次迭代时克隆结果集。
输入将是一个字符串，比如"abc"，输出将是所有可能的排列：
abc
acb
bac
bca
cba
cab

代码：

public static void permute(String s) {
    permute(s, 0);
}

private static void permute(String str, int left){
    if(left == str.length()-1) {
        System.out.println(str);
    } else {
        for(int i = left; i < str.length(); i++) {
            String s = swap(str, left, i);
            permute(s, left+1);
        }
    }
}

private static String swap(String s, int left, int right) {
    if (left == right)
        return s;

    String result = s.substring(0, left);
    result += s.substring(right, right+1);
    result += s.substring(left+1, right);
    result += s.substring(left, left+1);
    result += s.substring(right+1);
    return result;
}

同样的方法也可以应用于数组（而不是字符串）：

public static void main(String[] args) {
    int[] abc = {1,2,3};
    permute(abc, 0);
}
public static void permute(int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = index; i < arr.length; i++) {
            int[] permutation = arr.clone();
            permutation[index] = arr[i];
            permutation[i] = arr[index];
            permute(permutation, index + 1);
        }
    }
}
1
我知道这是一个非常非常古老的话题，甚至与今天的stackoverflow无关，但我仍然想为您贡献一个友好的javascript答案，原因很简单，它可以在您的浏览器中运行。
我还添加了debugger指令断点，以便您可以通过代码步进（需要chrome）来查看此算法的工作方式。在chrome中打开您的dev控制台（windows上为F12或mac上的CMD + OPTION + I），然后单击“运行代码片段”。这实现了与@WhirlWind在他的答案中提出的完全相同的算法。
您的浏览器应在debugger指令处暂停执行。使用F8继续执行代码。
逐步执行代码并查看其工作原理！ 

function permute(rest, prefix = []) {
  if (rest.length === 0) {
    return [prefix];
  }
  return (rest
    .map((x, index) => {
      const oldRest = rest;
      const oldPrefix = prefix;
      // the `...` destructures the array into single values flattening it
      const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
      const newPrefix = [...prefix, x];
      debugger;

      const result = permute(newRest, newPrefix);
      return result;
    })
    // this step flattens the array of arrays returned by calling permute
    .reduce((flattened, arr) => [...flattened, ...arr], [])
  );
}
console.log(permute([1, 2, 3]));

1

我在大一时想出了这两种算法（一种是递归算法，另一种是迭代算法），并用Python进行了实现（抱歉命名有些随意）：

def permute(x):
    m = [ord(i) for i in x]
    m.sort()
    count = 1
    print(count,''.join([chr(i) for i in m]))
    while (True):
        l = -1
        lgth = len(m)
        while (m[l] <= m[l-1]):
            l -= 1
            if l == -lgth:
                break
        if l == -lgth:
            break
        z = sorted(m[l-1:])
        k = m[l-1]
        z2 = z[:]
        z.reverse()
        b = z[z.index(k)-1]
        z2.remove(b)
        v = [b] + z2
        m[l-1:] = v
        count += 1
        print(count, ''.join([chr(i) for i in m]))

"""A Less-powerful solution: """

def permute_recursively(inp_list):
    if (len(inp_list) == 1):
        return [inp_list]
    else:
        x = permute_recursively(inp_list[1:])
        a = inp_list[0]
        z = []
        for i in x:
            for k in range(len(i) + 1):
                z.append(i[:k] + [a] + i[k:])
        return(z)

""" main section """

x = input("Enter the string: ")

#call to permute
permute(x)
print("****** End of permute ******\n")

#call to permute_recursively
count = 1
for i in permute_recursively(sorted(list(x))):
    print(count, ''.join(i))
    count += 1

第一个算法的特点：

  • 更加高效。
  • 可用于任何长度的输入（如果您有足够的时间和计算资源）。
  • 按照字符的ASCII值以字典顺序生成排列。
  • 几乎不使用内存。
  • 跳过生成任何重复项。
  • 生成确切的https://istack.dev59.com/NZ2vt.webp个排列，其中n是输入中字符的数量，i是任何重复字符的索引，m是索引为i的字符的重复次数。

第二个算法是递归的：

  • 效率较低。
  • 不能用于超出一定限制长度的输入，因为递归深度是有限的。
  • 不按字典顺序生成排列。
  • 需要大量内存，因为它需要存储生成的每个排列。
  • 生成重复项。
  • 生成确切的n!个输出。
1
这是我的Java解决方案：

public class CombinatorialUtils {

    public static void main(String[] args) {
        List<String> alphabet = new ArrayList<>();
        alphabet.add("1");
        alphabet.add("2");
        alphabet.add("3");
        alphabet.add("4");

        for (List<String> strings : permutations(alphabet)) {
            System.out.println(strings);
        }
        System.out.println("-----------");
        for (List<String> strings : combinations(alphabet)) {
            System.out.println(strings);
        }
    }

    public static List<List<String>> combinations(List<String> alphabet) {
        List<List<String>> permutations = permutations(alphabet);
        List<List<String>> combinations = new ArrayList<>(permutations);

        for (int i = alphabet.size(); i > 0; i--) {
            final int n = i;
            combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
        }
        return combinations;
    }

    public static <T> List<List<T>> permutations(List<T> alphabet) {
        ArrayList<List<T>> permutations = new ArrayList<>();
        if (alphabet.size() == 1) {
            permutations.add(alphabet);
            return permutations;
        } else {
            List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
            T addedElem = alphabet.get(0);
            for (int i = 0; i < alphabet.size(); i++) {
                for (List<T> permutation : subPerm) {
                    int index = i;
                    permutations.add(new ArrayList<T>(permutation) {{
                        add(index, addedElem);
                    }});
                }
            }
        }
        return permutations;
    }
}
0
以下是两个经典的Kotlin实现，递归和非递归堆算法实现：
非递归：
fun <T> permutationsHeapNonRecursive(list: List<T>): List<List<T>> {
    val result = mutableListOf<List<T>>()
    val c = Array(list.size) {0}
    result.add(list.toList())

    val tempList = list.toMutableList()
    var i = 1
    while (i < list.size) {
        if (c[i] < i) {
            if (i % 2 == 0)
                tempList[0] = tempList[i].also { tempList[i] = tempList[0] }
            else
                tempList[c[i]] = tempList[i].also { tempList[i] = tempList[c[i]] }
            result.add(tempList.toList())
            c[i] += 1
            i = 1
        }
        else {
            c[i] = 0
            i += 1
        }
    }
    return result
}

而且，递归：

private fun <T> permutationsHeapRecursiveInternal(k: Int, list: MutableList<T>, outList: MutableList<List<T>>) {
    if (k == 1) {
        outList.add(List<T>(list.size) {list[it]})
    }
    else {
        permutationsHeapRecursiveInternal(k - 1, list, outList)
        for (i in 0 until k-1) {
            if (k % 2 == 0)
                list[i] = list[k-1].also{ list[k-1] = list[i] }
            else
                list[0] = list[k-1].also{ list[k-1] = list[0] }
            permutationsHeapRecursiveInternal(k - 1, list, outList)
        }
    }
}

fun <T> permutationsHeapRecursive(list: List<T>): List<List<T>> {
    val result = mutableListOf<List<T>>()
    if (list.isNotEmpty()) {
        val tempList = MutableList<T>(list.size) { i -> list[i] }
        permutationsHeapRecursiveInternal(tempList.size, tempList, result)
    }
    return result
}

我已经对非递归版本进行了分析，并通过限制内存分配进行了一些调整，使其比递归版本更快。

0
以下是Heap's algorithm的通用实现（适用于int、char等）：
void generate<T>(int k, List<T> A, List<List<T>> result)
{
    if (k == 1)
    {
        result.Add(new List<T>(A)); 
        return;
    }
    for (int i = 0; i < k; i++)
    {
        generate(k - 1, A, result);
        if (k % 2 == 0)
            (A[i], A[k - 1]) = (A[k - 1], A[i]);
        else
            (A[0], A[k - 1]) = (A[k - 1], A[0]);
    }
}

使用它：

var permutations = new List<List<char>>();
List<char> A = new List<char>() { 'a', 'b', 'c', 'd'};
generate<char>(A.Count, A, permutations);
// The output is in permutations
int c = 0;
foreach (var item in permutations)
{
    c++;
    Console.Write(c + ". ");
    foreach (var element in item)
    {
        Console.Write(element);
    }
    Console.WriteLine();

}
0
作为C#扩展方法：
  • 避免在List()（假定由Array支持）的位置零插入。
  • 用更简单的list.Count == 0检查替换list.Count == 2。
  • 缺点是在递归期间使用了额外的参数。

用法：

List<List<string>> permutations = new List<string> { "A", "BB", "CCC" }.Permutations();

Debug.WriteLine(String.Join("; ", permutations.Select(p => string.Join(", ", p))));

输出：

A，BB，CCC；A，CCC，BB；BB，A，CCC；BB，CCC，A；CCC，A，BB；CCC，BB，A

方法：

static public List<List<T>> Permutations<T>(this List<T> list, List<T> prefillOpt = null) 
{
    List<List<T>> result = new List<List<T>>();

    if (list.Count == 0)
    {
        if (prefillOpt?.Any() == true)
            result.Add(prefillOpt.ToList()); // make a copy, owned by caller
    }
    else
    {
        prefillOpt = prefillOpt ?? new List<T>();

        for (int i = 0; i < list.Count; i++)
        {                    
            prefillOpt.Add(list[i]);

            int j = 0;
            result.AddRange(Permutations(list.Where(moot => j++ != i).ToList(), prefillOpt));
                    
            prefillOpt.RemoveAt(prefillOpt.Count - 1);
        }
    }
    return result;
}
你有注意到这个问题已经发布了11年，而且已经有35个答案了吗？ - Karl Knechtel
0
以下是用C++编写的非递归解决方案，按升序提供下一个排列，类似于std::next_permutation提供的功能：
void permute_next(vector<int>& v)
{
  if (v.size() < 2)
    return;

  if (v.size() == 2)
  { 
    int tmp = v[0];
    v[0] = v[1];
    v[1] = tmp;
    return;
  }

  // Step 1: find first ascending-ordered pair from right to left
  int i = v.size()-2;
  while(i>=0)
  { 
    if (v[i] < v[i+1])
      break;
    i--;
  }
  if (i<0) // vector fully sorted in descending order (last permutation)
  {
    //resort in ascending order and return
    sort(v.begin(), v.end());
    return;
  }

  // Step 2: swap v[i] with next higher element of remaining elements
  int pos = i+1;
  int val = v[pos];
  for(int k=i+2; k<v.size(); k++)
    if(v[k] < val && v[k] > v[i])
    {
      pos = k;
      val = v[k];
    }
  v[pos] = v[i];
  v[i] = val;

  // Step 3: sort remaining elements from i+1 ... end
  sort(v.begin()+i+1, v.end());
}
0

以下是 PHP 中的递归解决方案。WhirlWind 的帖子准确地描述了该逻辑。值得一提的是，生成所有排列的运行时间是阶乘时间，因此最好使用迭代方法来替代。

public function permute($sofar, $input){
  for($i=0; $i < strlen($input); $i++){
    $diff = strDiff($input,$input[$i]);
    $next = $sofar.$input[$i]; //next contains a permutation, save it
    $this->permute($next, $diff);
  }
}

strDiff函数接受两个字符串s1和s2，并返回一个新的字符串，其中包含s1中没有s2元素的所有内容（重复项有影响）。因此，strDiff('finish'，'i') => 'fnish'（第二个'i'未被删除）。
0
#!/usr/bin/env python
import time

def permutations(sequence):
  # print sequence
  unit = [1, 2, 1, 2, 1]

  if len(sequence) >= 4:
    for i in range(4, (len(sequence) + 1)):
      unit = ((unit + [i - 1]) * i)[:-1]
      # print unit
    for j in unit:
      temp = sequence[j]
      sequence[j] = sequence[0]
      sequence[0] = temp
      yield sequence
  else:
    print 'You can use PEN and PAPER'


# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']

print s

z = permutations(s)
try:
  while True:
    # time.sleep(0.0001)
    print next(z)
except StopIteration:
    print 'Done'

['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']
该解决方案表明您未按要求对字符串进行排列。第二个排列应为PYTHNO。 - Rahul Kadukar
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接