排列与有限重复算法 [英] Algorithm of Permutation with Limited Repetition

问题描述

有一个算法，列出所有与一个有限的重复的排列？如果有一个现有的Java库，这将是多好啊！

Is there an algorithm to list out all the permutations with a limited repetition? If there is an existing Java library, it would be so nice!

让我们说我们有3项 {A，B，C} 。我们要的2项置换。这将是<子> 3 P ₂ ：

Let's say we have 3 items {A, B, C}. We want a permutation of 2 items. It would be ₃P₂:

{A, B}
{A, C}
{B, A}
{B, C}
{C, A}
{C, B}

但是，如果我们允许两次最大重复。怎么会是怎样的呢？ （我真的不知道。）

But if we allow a maximum repetition of twice. How it would be like? (i don't really know.)

我试着成像，我们从一组获得的2置换 {A，A，B，B，C，C} 。这将是 ₆ P ₂ = 30。但是，我们必须要带走这些重复的。我已经通过手工完成它，它是9。我不知道如何从数学计算9。

I try to imaging we are getting a permutation of 2 from the set {A, A, B, B, C, C}. It would be ₆P₂ = 30. But we have to take away those duplicates. I have done it by hand and it is 9. I don't know how to calculate 9 from maths.

{A, A}
{A, B}
{A, C}
{B, B}
{B, A}
{B, C}
{C, C}
{C, A}
{C, B}

（其实<子> 3 P ₂ 为2的重复不是一个很好的例子，这是因为只有2中的排列元素。因此， ，有无限的重复是没有区别的。<子> 4 P <子> 3 为2的重复将是一个更好的例子，但是这将是艰难的，列出所有的排列。 ）的

(In fact ₃P₂ with a repetition of 2 is not a good example. It is because there are only 2 elements in the permutations. Therefore, there are no differences between an unlimited repetition. ₄P₃ with a repetition of 2 would be a nicer example. But it would be tough to list out all the permutations.)

为了说明一个更好的例子：<子> 4 P <子> 3 集 {A，B，C，D}

A better example for illustration: ₄P₃ of set {A, B, C, D}:

{A, B, C}
{A, B, D}
{A, C, B}
{A, C, D}
{A, D, B}
{A, D, C}
... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

和<子> 4 P <子> 3 集 {A，B，C，D} 用的重复限制2：

And ₄P₃ of set {A, B, C, D} with a repetition limit of 2:

{A, A, B}
{A, A, C}
{A, A, D}

{A, B, A}
{A, B, B}
{A, B, C}
{A, B, D}

{A, C, A}
{A, C, B}
{A, C, C}
{A, C, D}

{A, D, A}
{A, D, B}
{A, D, C}
{A, D, D}

... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

这里是一个网页说起类似的事情。但似乎它需要<子> N P <子> N （选择所有元素）。此外，我还需要一个算法来生成并列出了排列。

Here is a webpage talking about similar thing. But it seems it requires _nP_n (selecting all the elements). Also, i still need an algorithm to generate and list out the permutations.

感谢您的帮助！

有关规划的实施，其实有一种不聪明的办法。

For programming implementation, in fact there is a "not smart" approach.

有关集 {A，B，C，D} ，保持互补阵列 INT使用[0，0，0，0] ，它们是时间和每一元件所使用的号码。每一个元素选择时间增量计数，并通过数组的一个副本向前（下调用树）。然后用递归方法的启发 href="http://stackoverflow.com/a/4240323/1884546">，改变它允许无限制的重复（通过的没有的删除从元素集合中选择一个），并添加一个如果（使用[1] - = LIMIT）经过检查语句。

For set {A, B, C, D}, keep a complementary array int used[0, 0, 0, 0], which are the numbers of times each element is used. Increment the count every time an element is chosen, and pass a copy of the array forward (down the call tree). Then with the recursive approach inspired here, alter it to allow unlimited repetition (by not deleting the selected one from the element set), and add an if (used[i] <= LIMIT) checking statement after for.

这是不聪明并不够好，因为我们需要一个互补的阵列，并要求每次检查过的号码。

This is "not smart" and not good enough because we need a complementary array and require checking the used number every time.

推荐答案

那么，这是一个有点晚，但我有一个的 Java的组合数学库了GitHub上，将做到这一点。这里的基本用法：

Well, this is a little late, but I have a Java Combinatorics library up on GitHub that will do this. Here is the basic usage:

在你的项目中包含的依赖：

Include the dependency in your project:

<dependency>
  <groupId>com.xiantrimble.combinatorics</groupId>
  <artifactId>combinatorics</artifactId>
  <version>0.2.0</version>
<dependency>

然后从combinatoric工厂得到一个虚拟访问集合的排列：

Then iterate the permutations by getting a virtual collection from the combinatoric factory:

import com.xiantrimble.combinatorics.CombinatoricFactory;
import com.xiantrimble.combinatorics.CombinatoricFactoryImpl;
import com.xiantrimble.combinatorics.Combinatoric;
...
int k = 6;
int[] domain = {1,1,1,1,2,2,2,3,3,4};
// create a factory.
CombinatoricFactory factory = new CombinatoricFactoryImpl();
Combinatoric<Integer> permutations = factory.createPermutations(k,  domain);

for( Integer[] permutation : permutations ) {
  System.out.println(Arrays.toString(permutation));
}

在code没有做一个字典顺序，而是被朝试图尽量减少连续元素之间的变化减速，所以记住这一点。另外，还有一些在0.3.0-快照版本，它可以在Sonatype的的快照库一些改进。

The code does not do a dictionary order, but is instead geared toward trying to minimize the change between consecutive elements, so keep that in mind. Also, there are some improvements in the 0.3.0-SNAPSHOT version, which is available on Sonatype's snapshot repository.

这篇关于排列与有限重复算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！