создание вариаций без повторений/перестановок в 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 — содержит повторы)
Я был бы очень признателен, если бы кто-нибудь помог мне с этой проблемой, особенно предоставив код и подсказки.
Решение
Ключевое слово для поиска: перестановка.Существует множество свободно доступных исходных кодов, которые их выполняют.
Что касается отсутствия повторения, я предлагаю простой рекурсивный подход:для каждой цифры у вас есть выбор, включать ее в свой вариант или нет, поэтому ваша рекурсия учитывает цифры и разветвляется на два рекурсивных вызова, один из которых включает цифру, другой - исключает ее.Затем, после того как вы достигли последней цифры, каждая рекурсия по существу дает вам (уникальный, отсортированный) список цифр без повторений.Затем вы можете создать все возможные варианты этого списка и объединить все эти варианты для достижения конечного результата.
(То же, что сказал Даффимо:Я не буду предоставлять код для этого)
Расширенное примечание:рекурсия основана на 0/1 (исключение, включение), которое можно напрямую преобразовать в биты, следовательно, в целые числа.Следовательно, чтобы получить все возможные комбинации цифр без фактического выполнения самой рекурсии, вы можете просто использовать все 10-битные целые числа и перебирать их.Затем интерпретируйте числа так, чтобы установленный бит соответствовал включению в список цифры, которую необходимо переставить.
Другие советы
Вот мой Java-код.Не стесняйтесь спрашивать, если вы не понимаете.Главное здесь следующее:
- снова отсортировать массив символов.например:а1 а2 а3 б1 б2 б3 ....(а1 = а2 = а3)
- генерировать перестановку и всегда сохранять условие:индекс 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");
}
}
Я создал следующий код для генерации перестановок, где важен порядок и без повторений.Он использует дженерики для перестановки объектов любого типа:
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 следующим образом.
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 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 раз и т.д.Это означает, что для первых 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
...
и т. д. Обратите внимание, что первая строка присутствует из предыдущего шага, поэтому ее нельзя снова добавлять в сгенерированный набор.
Алгоритм рекурсивно делает именно то, что описано выше.Можно сгенерировать все 3628800 комбинаций за 10!, поскольку количество вложений совпадает с количеством элементов в массиве (это означает, что в вашем случае для 10 чисел оно задерживается примерно на 5 минут.на моем компьютере), и вам понадобится достаточно памяти, если вы хотите хранить все комбинации в массиве.
Решение есть.
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);
}
}
Интенсивность (количество тактов) алгоритма представляет собой сумму неполных факториалов числа членов.Таким образом, когда частичный набор снова считывается для создания следующего подмножества, возникает навес, поэтому интенсивность равна:
н!+ н!/2!+ н!/3!+ ...+ n!/(n-2)!+ н!(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!-1} для «индексации с нулем» или {1 и N!} для «индексации с единицей».
Создайте второй метод, содержащий цикл for, где нижняя граница равна 1, а верхняя граница — N!.например..«для (я;я <= N!;i++)» для каждого экземпляра цикла вызовите первый метод, передав i в качестве аргумента.
