Java에서 반복 / 순열없이 변형을 생성합니다
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
숫자 0-9로 만들어진 반복없이 모든 변형을 생성해야합니다.
그것들의 길이는 1에서 10까지가 될 수 있습니다. 나는 그것을 해결하는 방법, 특히 반복을 피하는 방법을 실제로 모른다.
예 : 변형 길이 : 4 개의 무작위 변형 : 9856, 8753, 1243, 1234 등 (하지만 9985- 반복을 포함하지 않음)
누군가가 그 문제를 도와 줄 수 있다면, 특히 코드와 단서를 제공한다면 정말 감사 할 것입니다.
해결책
찾아야 할 키워드는입니다 순열. 이를 수행하는 소스 코드가 자유롭게 사용 가능합니다.
반복을 무료로 유지하기 위해 간단한 재귀 접근법을 제안합니다. 각 숫자에 대해 변형에 맞게 선택할 수 있습니다. 따라서 재귀는 숫자와 포크를 두 개의 재귀 통화로 계산합니다. , 하나는 그것이 제외된다. 그런 다음 마지막 숫자에 도달 한 후 각 재귀는 본질적으로 반복없는 숫자의 (고유 한 정렬 된) 목록을 제공합니다. 그런 다음이 목록의 가능한 모든 순열을 생성하고 모든 순열을 결합하여 최종 결과를 달성 할 수 있습니다.
(Duffymo가 말한 것과 동일 : 나는 그것을 위해 코드를 공급하지 않을 것입니다)
고급 참고 : 재귀는 0/1 (제외, 포함)을 기반으로하며, 이는 비트로 직접 변환 될 수 있으므로 정수 번호입니다. 따라서 재귀 자체를 실제로 수행하지 않고 가능한 모든 숫자 조합을 얻으려면 모든 10 비트 정수 번호를 사용하여 반복 할 수 있습니다. 그런 다음 세트 비트가 목록에 숫자를 포함시켜야하는 숫자를 해석합니다.
다른 팁
여기 내 Java 코드가 있습니다. 이해하지 못하는지 물어보십시오. 여기서 요점은 다음과 같습니다.
- 문자 배열을 다시 정렬하십시오. 예 : A1 A2 A3 B1 B2 B3 .... (A1 = A2 = A3)
- 순열을 생성하고 항상 유지 조건 : A1의 색인 <index of 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");
}
}
순서가 중요하고 반복없이 순열을 생성하기위한 다음 코드를 만들었습니다. 모든 유형의 객체에 퍼져 나가기 위해 제네릭을 사용합니다.
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;
}
}
마법의 기능이 있다고 상상해보십시오. 숫자 배열이 주어지면 올바른 순열을 반환 할 것입니다.
해당 기능을 사용하여 하나의 여분의 숫자로 새로운 순열 목록을 생성하는 방법은 무엇입니까?
예,
내가 당신에게 불리는 함수를 주었다면 permute_three(char[3] digits), 그리고 나는 그것이 숫자에만 적용된다고 말합니다. 0, 1, 2, 당신은 어떻게 퍼뜨릴 수있는 함수를 쓸 수 있습니까? 0, 1, 2, 3, 주어진 것을 사용합니다 permute_three 기능?
...
당신이 그것을 해결하면, 당신은 무엇을 알아 차십니까? 일반화 할 수 있습니까?
사용 달러 이건 간단하다:
@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));
}
}
이에 대한 코드는 If-Else 문을 추가하여 복제가없는 코드와 유사합니다. 암호
위 코드에서 다음과 같이 for loop을 편집하십시오.
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;
}
나를 위해 일했습니다
반복이없는 순열은 정리를 기반으로하며, 결과의 양은 요소 수 (이 경우 번호)의 요인입니다. 당신의 경우 10! 10*9*8*7*6*5*4*3*2*1 = 3628800입니다. 왜 그것이 정확히 올바른지 증거는 세대에도 적합한 솔루션입니다. 음. 첫 번째 위치, 즉 왼쪽에서 10 개의 숫자를 가질 수 있습니다. 두 번째 위치에서는 9 개의 숫자 만 가질 수 있습니다. 한 숫자는 왼쪽의 위치에 있고 동일한 숫자 등을 반복 할 수 없기 때문에 (증거는 수학적 유도로 수행됩니다. ). 그렇다면 처음 10 개의 결과를 생성하는 방법은 무엇입니까? 나의 지식에 따르면, 그는 가장 간단한 방법은 주기적 변화를 사용하는 것입니다. 그것은 한 위치에서 왼쪽으로 이동하는 순서 (또는 원하는 경우 오른쪽)와 빈 장소에 올려 놓는 숫자를 의미합니다. 그것은 처음 10 개의 결과를 의미합니다.
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-1 숫자 만 10-1 번만 회전합니다. 2 단계에서 처음 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에 대한 모든 3628800 조합을 생성 할 수 있습니다 (케이스에서는 약 5 분 내 컴퓨터에 남아있는 경우 10 개의 숫자를 의미합니다). 충분한 메모리가 필요합니다. 모든 조합을 배열로 유지하려면.
해결책이 있습니다.
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);
}
}
알고리즘의 강도 (사이클 수)는 회원 수의 불완전한 계승의 합입니다. 따라서 부분 세트가 다시 읽어 다음 서브 세트를 생성하기 위해 다시 읽을 때 오버행이 있습니다. 강도는 다음과 같습니다.
N! + n!/2! + n!/3! + ... + n!/(n-2)! + N! (N-1)!
내 출신이 아닌 하나의 해결책이 있지만 매우 훌륭하고 정교합니다.
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);
}
}
}
나는 이것이 훌륭한 솔루션이라고 생각합니다.
간단한 유용한 순열 색인 지식
{0과 n! 사이에 인덱스 값이 주어지면 올바른 순열을 생성하는 메소드를 만듭니다. "Zero Indexed"또는 {1 및 n!}의 경우 -1} "One Indexed"의 경우.
하한이 1이고 상한은 n! 인 "루프 용"을 포함하는 두 번째 방법을 만듭니다. 예를 들어 .. "(i; i <= n!; i ++)" "루프의 모든 인스턴스에 대해 첫 번째 방법을 호출하여 I를 인수로 전달합니다.
