生成一组整数的不同大小的所有排列的算法？

-1

比方说，我有一个整数数组，例如[3,4,2,7,8,5]生成一组整数的不同大小的所有排列的算法？

我怎么会产生这个数组大小不同的排列？

像得到所有可能的2对，或所有可能的3组？ 4的？

我希望能够很快做到这一点。

2016-12-15 kmd12

@Imer Mercer：不是一个确切的副本。所有可能的组合！=所有可能的排列组合。 – AnT

对于与第一原理无关的语言方法：枚举大小为k的所有子集（对于k = 2，...，n，其中n是数组大小）。维基百科关于组合的文章在其enumeration上有一节。对于每个枚举子集，使用Johnson-Trotter algorithm来枚举它的排列。这种排列的总数非常快。例如，只有10个项目有9,864,090

许多语言都有库支持。例如，这是Python中的一个简单的编程练习（使用它的itertools模块）。下面是用于制造这样的排列的发电机：

import itertools 

def allPermutations(items): 
    n = len(items) 
    for k in range(2,n+1): 
     for combo in itertools.combinations(items,k): 
      for perm in itertools.permutations(combo): 
       yield perm

例如，list(allPermutations([3,4,2,7,8,5]))取值为[3,4,2,7,8,5]绘制所有1950这样的排列的列表。

来源

2016-12-16 01:09:13

您可以使用任何算法（如众所周知的Narayana algorithm）生成大小为N的所有排列。

现在，如果置换的这个总序列中只考虑前缀排列（一，一个，......，一个_ķ），其中一个 <一个 < ... < a _k，那么所有这样的排列的尾部将形成长度为N - k的所有可能排列的序列。

这样，通过对所有长度为N的排列进行单次传递，您可以生成长度为N或更短的所有排列组合。

这里是一个C++实现可能是什么样子

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    int a[] = { 2, 3, 4, 5, 7, 8 }; 

    do 
    { 
    for (auto ite = std::begin(a); ite != std::end(a); ++ite) 
     if (std::is_sorted(std::begin(a), ite)) 
     { 
     std::copy(ite, std::end(a), std::ostream_iterator<int>(std::cout)); 
     std::cout << std::endl; 
     } 

    } while (std::next_permutation(std::begin(a), std::end(a))); 
}

（我花了排序前您输入设置的自由。）

以上显然不是最优的，因为std::is_sorted内连续调用for周期将反复重新扫描/重新检查之前迭代中已经检查的内容。但是，这个实现只是为了说明的目的。

现在的问题是，您是否满意这些排列生成的顺序。上述方法不会按长度分组。

或者，您也可以通过all possible combinations迭代，然后就生成每个组合的所有可能的排列。

来源

2016-12-16 01:21:48 AnT

生成一组整数的不同大小的所有排列的算法？

回答

相关问题