java 在java中生成没有重复/排列的变化

generating Variations without repetitions / Permutations in java

提问by Raf Szalansky

I have to generate all variations without repetitions made of digits 0 - 9.

我必须生成所有变体而不重复由数字 0 - 9 组成。

Length of them could be from 1 to 10. I really don't know how to solve it, especially how to avoid repetitions.

它们的长度可以从1到10。我真的不知道如何解决它，尤其是如何避免重复。

Example: length of variations: 4 random variations: 9856, 8753, 1243, 1234 etc. (but not 9985 - contains repetition)

示例：变体长度：4 个随机变体：9856、8753、1243、1234 等（但不是 9985 - 包含重复）

I would be really grateful if somebody can help me with that issue, especially giving some code and clues.

如果有人能帮助我解决这个问题，我将不胜感激，尤其是提供一些代码和线索。

采纳答案by Frank

The keyword to look for is permutation. There is an abundance of source code freely available that performs them.

要查找的关键字是permutation。有大量免费的源代码可以执行它们。

As for keeping it repetition free I suggest a simple recursive approach: for each digit you have a choice of taking it into your variation or not, so your recursion counts through the digits and forks into two recursive calls, one in which the digit is included, one in which it is excluded. Then, after you reached the last digit each recursion essentially gives you a (unique, sorted) list of repetition-free digits. You can then create all possible permutations of this list and combine all of those permutations to achieve your final result.

至于保持它没有重复，我建议采用一种简单的递归方法：对于每个数字，您可以选择是否将其纳入您的变体中，因此您的递归将通过数字和分叉为两个递归调用，其中包含数字，其中一个它被排除在外。然后，在您到达最后一位数字后，每次递归本质上都会为您提供一个（唯一的、已排序的）无重复数字列表。然后，您可以创建此列表的所有可能排列并组合所有这些排列以实现最终结果。

(Same as duffymo said: I won't supply code for that)

（正如 duffymo 所说：我不会为此提供代码）

Advanced note: the recursion is based on 0/1 (exclusion, inclusion) which can directly be translated to bits, hence, integer numbers. Therefore, in order to get all possible digit combinations without actually performing the recursion itself you could simply use all 10-bit integer numbers and iterate through them. Then interpret the numbers such that a set bit corresponds to including the digit in the list that needs to be permuted.

高级说明：递归基于 0/1（排除、包含），可以直接转换为位，因此为整数。因此，为了在不实际执行递归本身的情况下获得所有可能的数字组合，您可以简单地使用所有 10 位整数并遍历它们。然后解释这些数字，使得设置位对应于在列表中包含需要排列的数字。

回答by hqt

Here is my Java code. Feel free to ask if you don't understand. The main point here is:

这是我的 Java 代码。如果您不明白，请随时提问。这里的要点是：

1. sort again character array. for example: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
2. generate permutation and always keep condition: index of a1 < index of a2 < index of a3 ...

1. 再次对字符数组进行排序。例如：a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
2. 生成排列并始终保持条件：a1 的索引 < a2 的索引 < a3 的索引 ...

import java.util.Arrays;

public class PermutationDup {

    public void permutation(String s) {
        char[] original = s.toCharArray();
        Arrays.sort(original);
        char[] clone = new char[s.length()];
        boolean[] mark = new boolean[s.length()];
        Arrays.fill(mark, false);
        permute(original, clone, mark, 0, s.length());
    }

    private void permute(char[] original, char[] clone, boolean[] mark, int length, int n) {
        if (length == n) {
            System.out.println(clone);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (mark[i] == true) continue;
            // dont use this state. to keep order of duplicate character
            if (i > 0 && original[i] == original[i-1] && mark[i-1] == false) continue;
            mark[i] = true;
            clone[length] = original[i];
            permute(original, clone, mark, length+1, n);
            mark[i] = false;
        }

    }

    public static void main(String[] args) {
        PermutationDup p = new PermutationDup();
        p.permutation("abcab");
    }
}

回答by uldall

I have created the following code for generating permutations where ordering is important and with no repetition. It makes use of generics for permuting any type of object:

我创建了以下代码来生成排序很重要且没有重复的排列。它利用泛型来排列任何类型的对象：

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations {

    public static <T> Collection<List<T>> generatePermutationsNoRepetition(Set<T> availableNumbers) {
        Collection<List<T>> permutations = new HashSet<>();

        for (T number : availableNumbers) {
            Set<T> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                Collection<List<T>> childPermutations = generatePermutationsNoRepetition(numbers);
                for (List<T> childPermutation : childPermutations) {
                    List<T> permutation = new ArrayList<>();
                    permutation.add(number);
                    permutation.addAll(childPermutation);
                    permutations.add(permutation);
                }
            } else {
                List<T> permutation = new ArrayList<>();
                permutation.add(number);
                permutations.add(permutation);
            }
        }

        return permutations;
    }
}

回答by Craig Cantrell

Brief helpful permutation indexing Knowledge

简要有用的排列索引知识

Create a method that generates the correct permutation, given an index value between {0 and N! -1} for "zero indexed" or {1 and N!} for "one indexed".

给定一个介于 {0 和 N! 之间的索引值，创建一个生成正确排列的方法！-1} 表示“零索引”或 {1 和 N！} 表示“一索引”。

Create a second method containing a "for loop" where the lower bound is 1 and the upper bound is N!. eg.. "for (i; i <= N!; i++)" for every instance of the loop call the first method, passing i as the argument.

创建包含“for 循环”的第二个方法，其中下限为 1，上限为 N！。例如..“for (i; i <= N!; i++)”对于循环的每个实例调用第一个方法，将 i 作为参数传递。

回答by hariprasad

Permutation without repetition is based on theorem, that amount of results is factorial of count of elements (in this case numbers). In your case 10! is 10*9*8*7*6*5*4*3*2*1 = 3628800. The proof why it is exactly right is right solution for generation also. Well so how. On first position i.e. from left you can have 10 numbers, on the second position you can have only 9 numbers, because one number is on the position on the left and we cannot repeat the same number etc. (the proof is done by mathematical induction). So how to generate first ten results? According my knowledges, he simplest way is to use cyclic shift. It means the order of number shift to the left on one position (or right if you want) and the number which overflow to put on the empty place. It means for first ten results:

没有重复的排列基于定理，结果的数量是元素计数的阶乘（在这种情况下是数字）。在你的情况下 10！是 10*9*8*7*6*5*4*3*2*1 = 3628800。证明为什么它是完全正确的也是生成正确的解决方案。那么如何。在第一个位置，即从左边开始你可以有 10 个数字，在第二个位置你只能有 9 个数字，因为一个数字在左边的位置上，我们不能重复相同的数字等等（证明是通过数学归纳法完成的）。那么如何生成前十个结果呢？据我所知，他最简单的方法是使用循环移位。这意味着数字的顺序在一个位置上向左移动（如果需要，也可以向右移动），溢出的数字放在空的地方。这意味着前十个结果：

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 7 6
...

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 9 1 1
5 4 3 2 1 10 9 8 7 6
...

The first line is basic sample, so it is the good idea to put it into set before generation. Advantage is, that in the next step you will have to solve the same problem to avoid undesirable duplicities.

第一行是基本样本，所以最好在生成之前将其放入集合。优点是，在下一步中，您必须解决相同的问题，以避免出现不受欢迎的重复。

In next step recursively rotate only 10-1 numbers 10-1 times etc. It means for first 9 results in step two:

在下一步中，仅递归旋转 10-1 个数字 10-1 次等。这意味着前 9 个结果在第二步中：

10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
...

10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 8 2 1
...

etc, notice, that first line is present from previous step, so it must not be added to generated set again.

等等，请注意，第一行来自上一步，因此不得再次将其添加到生成集中。

Algorithm recursively doing exactly that, what is explained above. It is possible to generate all the 3628800 combinations for 10!, because number of nesting is the same as number of elements in array (it means in your case for 10 numbers it lingers about 5min. on my computer) and you need have enough memory if you want to keep all combinations in array.

算法递归地做到这一点，上面已经解释过。可以为 10! 生成所有 3628800 种组合，因为嵌套数与数组中的元素数相同（这意味着在您的情况下，10 个数字在我的计算机上停留约 5 分钟）并且您需要有足够的内存如果您想将所有组合保留在数组中。

There is solution.

有解决方案。

package permutation;

/** Class for generation amount of combinations (factorial)
 * !!! this is generate proper permutations without repeating and proper amount (po?et) of rows !!!
 *
 * @author hariprasad
 */
public class TestForPermutationII {
  private static final String BUMPER = "*";
  private static int counter = 0;
  private static int sumsum = 0;
  // definitoin of array for generation
  //int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int[] testsimple = {1, 2, 3, 4, 5};
  private int ELEMNUM = testsimple.length;
  int[][] shuff;

  private String gaps(int len) {
    String addGap = "";
    for(int i=0; i <len; i++)
      addGap += "  ";
    return addGap;
  }

  /** Factorial computing */
  private int fact(int num) {
    if (num > 1) {
      return num * fact(num - 1);
    } else {
      return 1;
    }
  }

  /** Cyclic shift position to the left */  
  private int[] lShiftPos(int[] arr, int pos) {
    int[] work = new int[ELEMNUM];
    int offset = -1;
    for (int jj = 0; jj < arr.length; jj++) {
      if (jj < pos) {
        work[jj] = arr[jj];
      } else if (jj <= arr.length - 1) {
        if (jj == pos) {
          offset = arr[pos]; // last element
        }
        if (jj != (arr.length - 1)) {
          work[jj] = arr[jj + 1];
        } else {
          work[jj] = offset;
        }
      }
    }
    return work;
  }

  private String printBuff(int[] buffer) {
    String res = "";
    for (int i= 0; i < buffer.length; i++) {
      if (i == 0) 
        res += buffer[i];
      else
        res += ", " + buffer[i];
    }
    return res;
  };

  /** Recursive generator for arbitrary length of array */
  private String permutationGenerator(int pos, int level) {
    String ret = BUMPER;
    int templen = counter;
    int[] work = new int[ELEMNUM];
    int locsumread = 0;
    int locsumnew = 0;
    //System.out.println("\nCalled level: " + level);

    for (int i = 0; i <= templen; i++) {
      work = shuff[i];
      sumsum++;
      locsumread++;
      for (int ii = 0; ii < pos; ii++) {
        counter++;
        sumsum++;
        locsumnew++;
        work = lShiftPos(work, level); // deep copy
        shuff[counter] = work;
      }
    }

    System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew);
    // if level == ELEMNUM-2, it means no another shift
    if (level < ELEMNUM-2) {
      ret = permutationGenerator(pos-1, level+1);
      ret = "Level " + level + " end.";
      //System.out.println(ret);
    }
    return ret;
  }

  public static void main(String[] argv) {
    TestForPermutationII test = new TestForPermutationII();
    counter = 0;
    int len = test.testsimple.length;
    int[] work = new int[len];

    test.shuff = new int[test.fact(len)][];

    //initial
    test.shuff[counter] = test.testsimple;
    work = test.testsimple; // shalow copy

    test.shuff = new int[test.fact(len)][];
    counter = 0;
    test.shuff[counter] = test.testsimple;
    test.permutationGenerator(len-1, 0);

    for (int i = 0; i <= counter; i++) {
      System.out.println(test.printBuff(test.shuff[i]));
    }

    System.out.println("Counter, cycles: " + counter + ", " + sumsum);
  }
}

Intensity (number of cycles) of algorithm is sum of incomplete factorials of number of members. So there is overhang when partial set is again read to generate next subset, so intensity is:

算法的强度（循环数）是成员数的不完全阶乘之和。因此，当再次读取部分集以生成下一个子集时会出现悬垂，因此强度为：

n! + n!/2! + n!/3! + ... + n!/(n-2)! + n!(n-1)!

啊！+ n!/2! + n!/3! + ... + n!/(n-2)! + n!(n-1)!

回答by hariprasad

There is one solution which is not from mine, but it is very nice and sophisticated.

有一种解决方案不是我的，但它非常好和复杂。

    package permutations;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * @author Vladimir Hajek
 *
 */
public class PermutationSimple {
    private static final int MAX_NUMBER = 3;

    Set<String> results = new HashSet<>(0);

    /**
     * 
     */
    public PermutationSimple() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param availableNumbers
     * @return
     */
    public static List<String> generatePermutations(Set<Integer> availableNumbers) {
        List<String> permutations = new LinkedList<>();

        for (Integer number : availableNumbers) {
            Set<Integer> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                List<String> childPermutations = generatePermutations(numbers);
                for (String childPermutation : childPermutations) {
                    String permutation = number + childPermutation;
                    permutations.add(permutation);
                }
            } else {
                permutations.add(number.toString());
            }
        }

        return permutations;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Set<Integer> availableNumbers = new HashSet<>(0);

        for (int i = 1; i <= MAX_NUMBER; i++) {
            availableNumbers.add(i);
        }

        List<String> permutations = generatePermutations(availableNumbers);
        for (String permutation : permutations) {
            System.out.println(permutation);
        }

    }
}

I think, this is the excellent solution.

我认为，这是极好的解决方案。

回答by Chii

Imagine you had a magical function - given an array of digits, it will return you the correct permutations.

想象一下你有一个神奇的函数——给定一个数字数组，它会返回正确的排列。

How can you use that function to produce a new list of permutations with just one extra digit?

您如何使用该函数生成一个新的排列列表，并且只增加一个数字？

e.g.,

例如，

if i gave you a function called permute_three(char[3] digits), and i tell you that it only works for digits 0, 1, 2, how can you write a function that can permute 0, 1, 2, 3, using the given permute_threefunction?

如果我给了你一个名为 的函数permute_three(char[3] digits)，我告诉你它只适用于数字0, 1, 2，你怎么能用给定的函数编写一个可以置换0, 1, 2,3的permute_three函数？

...

...

once you solved that, what do you notice? can you generalize it?

一旦你解决了这个问题，你注意到了什么？你能概括一下吗？

回答by dfa

using Dollarit is simple:

使用Dollar很简单：

@Test
public void generatePermutations() {
    // digits is the string "0123456789"
    String digits = $('0', '9').join();

    // then generate 10 permutations
    for (int i : $(10)) {
        // shuffle, the cut (0, 4) in order to get a 4-char permutation
        System.out.println($(digits).shuffle().slice(4));
    }
}

回答by abhi120

The code for this is similar to the one without duplicates, with the addition of an if-else statement.Check this code

此代码类似于没有重复的代码，但添加了一条 if-else 语句。检查此代码

In the above code,Edit the for loop as follows

在上面的代码中，编辑for循环如下

for (j = i; j <= n; j++)
{

if(a[i]!=a[j] && !is_duplicate(a,i,j))              
    {
        swap((a+i), (a+j));
        permute(a, i+1, n);
        swap((a+i), (a+j)); 
    }
    else if(i!=j)  {}  // if no duplicate is present , do nothing           
    else permute(a,i+1,n);  // skip the ith character
}

bool is_duplicate(int *a,int i,int j) 
{
     if a[i] is present between a[j]...a[i] 
        return 1;
    otherwise
        return 0;

}

worked for me

对我来说有效