生成所有独特的排列 [英] Generate all unique permutations

问题描述

我的工作中，我给出了一些，需要的一个问题
发现在该号码的数字每一个可能的排列。对于
例如，如果我给 20 ，答案应该是： 20 和 02 。我知道
有 N！可能的排列，我已经瓜分了
号，使得每个数字是在阵列的元件。我的问题是：
我怎么能遍历这个数组生成每一个可能的
一个数字，是至少2位长，但没有更多的组合
超过6。

I am working on a problem in which I am given a number and need to find every possible permutation of the digits in that number. For example, if I am given 20, the answer would be: 20 and 02. I know that there are n! possible permutations, and I have divided up the numbers so that each digit is an element in an array. My question is: How can I loop through this array to generate every possible combination of a number that is at least 2 digits long but no more than 6.

推荐答案

说出 N 个别数字的长度的数组 N 。然后生成排列的问题归结为：

Say the n individual digits are in an array of length n. Then the problem of generating the permutations boils down to:

1. 选择的 N 位数作为第一个数字打印之一。


2. 置换剩余 N-1 数字。

1. Choosing one of the n digits as the first digit to print.
2. Permuting the remaining n-1 digits.

一个递归。

伪code这样的递归函数置换会是这样的：

The pseudocode for such a recursive function permute would be something like:

List permute (Array digits)
{
  List permutations = /* initialize an empty list */

  for (i=0; i<n; i++)
    {
      firstDigit = digit[i];
      Array otherDigits = /* array containing all digits except firstDigit.  */
      List subPermutations = permute(otherDigits);
      /* prepend firstDigit into each element of 'subPermutations' */
      /* add all elements of 'subPermutations' to the list 'permutations' */
    }
  return permutations;
}

然后只需拨打置换并打印出清单，或者其他任何与它。

Then simply call permute and print out the list, or do whatever else with it.

编辑：您还需要处理的边缘情况置换 ING 1位数

You also need to handle the edge case of permuteing 1 digit.

我觉得这已经是'功课'太多的信息：）

I think this is already too much information for 'homework' :)

这篇关于生成所有独特的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！