Я хотел бы получить всю комбинацию числа без повторения. Например, 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. Я пытался найти простую схему, но не смог. Я нарисовал для него график/дерево, и это кричит об использовании рекурсии. Но я хотел бы сделать это без рекурсии, если это возможно.
Кто-нибудь может помочь мне сделать это?
Вот общий счетчик перестановок, который я написал год назад. Он также может производить «подперестановки»:
public class PermUtil <T> {
private T[] arr;
private int[] permSwappings;
public PermUtil(T[] arr) {
this(arr,arr.length);
}
public PermUtil(T[] arr, int permSize) {
this.arr = arr.clone();
this.permSwappings = new int[permSize];
for(int i = 0;i < permSwappings.length;i++)
permSwappings[i] = i;
}
public T[] next() {
if (arr == null)
return null;
T[] res = Arrays.copyOf(arr, permSwappings.length);
//Prepare next
int i = permSwappings.length-1;
while (i >= 0 && permSwappings[i] == arr.length - 1) {
swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
permSwappings[i] = i;
i--;
}
if (i < 0)
arr = null;
else {
int prev = permSwappings[i];
swap(i, prev);
int next = prev + 1;
permSwappings[i] = next;
swap(i, next);
}
return res;
}
private void swap(int i, int j) {
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
Идея моего алгоритма заключается в том, что любая перестановка может быть выражена как уникальная последовательность команд обмена. Например, для ‹A,B,C> последовательность замены 012 оставляет все элементы на месте, в то время как 122 начинается с замены индекса 0 на индекс 1, затем меняет местами 1 на 2, а затем меняет местами 2 на 2 (т. е. оставляет его в место). Это приводит к перестановке BCA.
Это представление изоморфно представлению перестановки (т. е. отношение один к одному), и его очень легко «увеличить» при обходе пространства перестановок. Для 4 элементов он начинается с 0123 (ABCD) и заканчивается на 3333 (DABC).
Вы должны использовать тот факт, что когда вы хотите, чтобы все перестановки N чисел были N! возможности. Поэтому каждое число x из 1..N! кодирует такую перестановку. Вот пример, который итеративно выводит все перестановки жала.
private static void printPermutationsIterative(String string){
int [] factorials = new int[string.length()+1];
factorials[0] = 1;
for (int i = 1; i<=string.length();i++) {
factorials[i] = factorials[i-1] * i;
}
for (int i = 0; i < factorials[string.length()]; i++) {
String onePermutation="";
String temp = string;
int positionCode = i;
for (int position = string.length(); position > 0 ;position--){
int selected = positionCode / factorials[position-1];
onePermutation += temp.charAt(selected);
positionCode = positionCode % factorials[position-1];
temp = temp.substring(0,selected) + temp.substring(selected+1);
}
System.out.println(onePermutation);
}
}
В общем случае любой рекурсивный алгоритм всегда можно свести к итеративному за счет использования структур данных стека или очереди.
Для этой конкретной проблемы может быть более поучительно взглянуть на алгоритм C++ STL std::next_permutation. . По словам Томаса Геста из wordaligned.org, базовая реализация выглядит следующим образом:
template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
if (first == last)
return false;
Iter i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
Iter ii = i;
--i;
if (*i < *ii)
{
Iter j = last;
while (!(*i < *--j))
{}
std::iter_swap(i, j);
std::reverse(ii, last);
return true;
}
if (i == first)
{
std::reverse(first, last);
return false;
}
}
}
Обратите внимание, что он не использует рекурсию и его относительно просто перевести на другой C-подобный язык, такой как Java. Вы можете прочитать об std::iter_swap, std::reverse и двунаправленные итераторы (то, что Iter представляет в этом коде).
Написать рекурсивную перестановку несложно, но для этого требуется экспортировать перестановки из глубоко вложенных циклов. (Это интересное упражнение.) Мне нужна была версия, которая переставляла строки вместо анаграмм. Я написал версию, реализующую Iterable<String>, чтобы ее можно было использовать в циклах foreach. Его можно легко адаптировать к другим типам, таким как int[] или даже к универсальному типу <T[]>, изменив конструктор и тип атрибута "массив".
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An implicit immutable collection of all permutations of a string with an
* iterator over the permutations.<p> implements Iterable<String>
* @see #StringPermutation(String)
*/
public class StringPermutation implements Iterable<String> {
// could implement Collection<String> but it's immutable, so most methods are essentially vacuous
protected final String string;
/**
* Creates an implicit Iterable collection of all permutations of a string
* @param string String to be permuted
* @see Iterable
* @see #iterator
*/
public StringPermutation(String string) {
this.string = string;
}
/**
* Constructs and sequentially returns the permutation values
*/
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
char[] array = string.toCharArray();
int length = string.length();
int[] index = (length == 0) ? null : new int[length];
@Override
public boolean hasNext() {
return index != null;
}
@Override
public String next() {
if (index == null) throw new NoSuchElementException();
for (int i = 1; i < length; ++i) {
char swap = array[i];
System.arraycopy(array, 0, array, 1, i);
array[0] = swap;
for (int j = 1 ; j < i; ++j) {
index[j] = 0;
}
if (++index[i] <= i) {
return new String(array);
}
index[i] = 0;
}
index = null;
return new String(array);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
Большинство примеров, которые я видел до сих пор, были либо слишком сложными, либо с использованием строк, либо с использованием свопов, поэтому я решил сделать один, который является итеративным, интуитивно понятным, универсальным и свободным от свопов.
public static <T> List<List<T>> permutations(List<T> es){
List<List<T>> permutations = new ArrayList<List<T>>();
if(es.isEmpty()){
return permutations;
}
// We add the first element
permutations.add(new ArrayList<T>(Arrays.asList(es.get(0))));
// Then, for all elements e in es (except from the first)
for (int i = 1, len = es.size(); i < len; i++) {
T e = es.get(i);
// We take remove each list l from 'permutations'
for (int j = permutations.size() - 1; j >= 0; j--) {
List<T> l = permutations.remove(j);
// And adds a copy of l, with e inserted at index k for each position k in l
for (int k = l.size(); k >= 0; k--) {
ArrayList<T> ts2 = new ArrayList<>(l);
ts2.add(k, e);
permutations.add(ts2);
}
}
}
return permutations;
}
Пример: нам нужны все перестановки [a,b,c]
Мы добавляем a и получаем [a] // [b,c] оставшиеся
Мы берем a из списка и добавляем [a,b ] и [b,a] // [c] осталось
Удаляем [b,a] и вставляем [b,a,c], [b,c,a], [c,b,a] а затем мы удаляем [a,b] и вставляем [a,b,c], [a,c,b], [c,a,b]
Вот общие и итеративные классы генератора перестановок, kpermutation и комбинаций, которые я написал на основе реализаций здесь и здесь. Мои классы используют их как внутренние классы. Они также реализуют Iterable Interface, чтобы быть доступным для доступа.
List<String> objects = new ArrayList<String>();
objects.add("A");
objects.add("B");
objects.add("C");
Permutations<String> permutations = new Permutations<String>(objects);
for (List<String> permutation : permutations) {
System.out.println(permutation);
}
Combinations<String> combinations = new Combinations<String>(objects, 2);
for (List<String> combination : combinations) {
System.out.println(combination);
}
KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
for (List<String> kPermutation : kPermutations) {
System.out.println(kPermutation);
}
Класс комбинаций:
public class Combinations<T> implements Iterable<List<T>> {
CombinationGenerator cGenerator;
T[] elements;
int[] indices;
public Combinations(List<T> list, int n) {
cGenerator = new CombinationGenerator(list.size(), n);
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return cGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = cGenerator.getNext();
List<T> combination = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
combination.add(elements[indices[i]]);
}
return combination;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class CombinationGenerator {
private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;
//------------
// Constructor
//------------
public CombinationGenerator(int n, int r) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
if (r > n) {
throw new IllegalArgumentException("Subset length can not be greater than set length");
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial(n);
BigInteger rFact = getFactorial(r);
BigInteger nminusrFact = getFactorial(n - r);
total = nFact.divide(rFact.multiply(nminusrFact));
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//-----------------------------
// Are there more combinations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------------------------
// Return total number of combinations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
Класс перестановок:
public class Permutations<T> implements Iterable<List<T>> {
PermutationGenerator pGenerator;
T[] elements;
int[] indices;
public Permutations(List<T> list) {
pGenerator = new PermutationGenerator(list.size());
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return pGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = pGenerator.getNext();
List<T> permutation = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
permutation.add(elements[indices[i]]);
}
return permutation;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class PermutationGenerator {
private int[] a;
private BigInteger numLeft;
private BigInteger total;
//-----------------------------------------------------------
// Constructor. WARNING: Don't make n too large.
// Recall that the number of permutations is n!
// which can be very large, even when n is as small as 20 --
// 20! = 2,432,902,008,176,640,000 and
// 21! is too big to fit into a Java long, which is
// why we use BigInteger instead.
//----------------------------------------------------------
public PermutationGenerator(int n) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
a = new int[n];
total = getFactorial(n);
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of permutations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//------------------------------------
// Return total number of permutations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//-----------------------------
// Are there more permutations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next permutation (algorithm from Rosen p. 284)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int temp;
// Find largest index j with a[j] < a[j+1]
int j = a.length - 2;
while (a[j] > a[j + 1]) {
j--;
}
// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
int k = a.length - 1;
while (a[j] > a[k]) {
k--;
}
// Interchange a[j] and a[k]
temp = a[k];
a[k] = a[j];
a[j] = temp;
// Put tail end of permutation after jth position in increasing order
int r = a.length - 1;
int s = j + 1;
while (r > s) {
temp = a[s];
a[s] = a[r];
a[r] = temp;
r--;
s++;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
И класс KPermutations, который на самом деле использует классы Permutations и Combinations:
public class KPermutations<T> implements Iterable<List<T>> {
Combinations<T> combinations;
public KPermutations(List<T> list, int k) {
if (k<1){
throw new IllegalArgumentException("Subset length k must me at least 1");
}
combinations = new Combinations<T>(list, k);
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
Iterator<List<T>> it = combinations.iterator();
Permutations<T> permutations = new Permutations<T>(combinations.iterator().next());
// Has more combinations but no more permutation for current combination
public boolean hasNext() {
if (combinations.iterator().hasNext() && !permutations.iterator().hasNext()){
permutations = new Permutations<T>(combinations.iterator().next());
return true;
}
//Has more permutation for current combination
else if (permutations.iterator().hasNext()){
return true;
}
// No more combination and permutation
return false;
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return permutations.iterator().next();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
Здесь у меня есть решение в scala, которое можно было бы использовать из java, но можно реализовать с гораздо большим количеством кода. в Java также, чтобы позволить использовать итератор для упрощенного цикла for:
for (List<Integer> list: permutations)
doSomething (list);
Чтобы обеспечить упрощенный цикл for, нам нужно реализовать Iterable, что означает, что мы должны предоставить метод, который возвращает итератор, который является другим интерфейсом, что означает, что мы должны реализовать 3 метода: hasNext (); следующий (); и удалить ();
import java.util.*;
class PermutationIterator <T> implements Iterator <List <T>> {
private int current = 0;
private final List <T> lilio;
public final long last;
public PermutationIterator (final List <T> llo) {
lilio = llo;
long product = 1;
for (long p = 1; p <= llo.size (); ++p)
product *= p;
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private long fac (long l)
{
for (long i = l - 1L; i > 1L; --i)
l *= i;
return l;
}
/**
new version, which produces permutations in increasing order:
*/
private List <T> get (final long code, final List <T> list) {
if (list.isEmpty ())
return list;
else
{
int len = list.size (); // len = 4
long max = fac (len); // max = 24
long divisor = max / len; // divisor = 6
int i = (int) (code / divisor); // i = 2
List <T> second = new ArrayList <T> (list.size ());
second.addAll (list);
T el = second.remove (i);
List <T> tt = new ArrayList <T> ();
tt.add (el);
tt.addAll (get (code - divisor * i, second));
return tt;
}
}
public List <T> get (final int code)
{
return get (code, lilio);
}
}
class PermutationIterable <T> implements Iterable <List <T>> {
private List <T> lilio;
public PermutationIterable (List <T> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new PermutationIterator <T> (lilio);
}
private long invers (final List <T> pattern, final List <T> matcher)
{
if (pattern.isEmpty ())
return 0L;
T first = pattern.get (0);
int idx = matcher.indexOf (first);
long l = (pattern.size () - 1L) * idx;
pattern.remove (0);
matcher.remove (idx);
return l + invers (pattern, matcher);
}
/**
make a deep copy, since the called method will destroy the parameters
*/
public long invers (final List <T> lt)
{
List <T> copy = new ArrayList <T> (lilio.size ());
copy.addAll (lilio);
return invers (lt, copy);
}
}
class PermutationIteratorTest {
public static List <Integer> genList (int... a) {
List <Integer> li = new ArrayList <Integer> ();
for (int i: a)
li.add (i);
return li;
}
public static void main (String[] args) {
List <Integer> il = new ArrayList <Integer> ();
// autoboxing, add '0' to 'z' as Character:
for (int c = 0; c < 3; ++c)
{
il.add (c);
}
PermutationIterable <Integer> pi = new PermutationIterable <Integer> (il);
for (List<Integer> li: pi)
show (li);
System.out.println ("-again-");
// do it a second time:
for (List <Integer> li: pi)
show (li);
// test the inverse:
System.out.println ("for (2,1,0) expecting 5 ?= " + pi.invers (genList (2, 1, 0)));
System.out.println ("for (2,0,1) expecting 4 ?= " + pi.invers (genList (2, 0, 1)));
System.out.println ("for (1,0,2) expecting 3 ?= " + pi.invers (genList (1, 2, 0)));
System.out.println ("for (1,2,0) expecting 2 ?= " + pi.invers (genList (1, 0, 2)));
System.out.println ("for (0,2,1) expecting 1 ?= " + pi.invers (genList (0, 2, 1)));
System.out.println ("for (0,1,2) expecting 0 ?= " + pi.invers (genList (0, 1, 2)));
Random r = new Random ();
PermutationIterator <Integer> pitor = (PermutationIterator <Integer>) pi.iterator ();
for (int i = 0; i < 10; ++i)
{
int rnd = r.nextInt ((int) pitor.last);
List <Integer> rli = pitor.get (rnd);
show (rli);
}
}
public static void show (List <?> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o);
System.out.println (")");
}
}
PermutationIterator содержит дополнительный общедоступный метод public List <T> get (final int code), который удобен, если вы хотите выбрать определенную перестановку по индексу, например, случайным образом. Вы знаете размер (последний) и поэтому можете выполнить перестановку допустимого диапазона по индексу.
PermutationIterable содержит метод «invers», который будет генерировать противоположное: индекс определенной перестановки.
Внутри invers и get работают рекурсивно, но все перестановки не производятся рекурсивно, так что это не должно быть проблемой даже для больших перестановок. Обратите внимание, что для 21 элемента вы превышаете размер longs, а 20 шагов рекурсии вообще не должны быть проблемой.
Вы можете использовать Factoradics (вы можете увидеть реализацию здесь) или L-алгоритм Кнута, генерирующий все перестановки. Ниже приведена реализация последнего:
public class Perm {
public static void main(String... args) {
final int N = 5;
int[] sequence = new int[N];
for (int i = 0; i < N; i++) {
sequence[i] = i + 1;
}
printSequence(sequence);
permutations(sequence);
}
private static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
private static void swap(int[] elements, int i, int j) {
int temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* Reverses the elements of an array (in place) from the start index to the end index
*/
private static void reverse(int[] array, int startIndex, int endIndex) {
int size = endIndex + 1 - startIndex;
int limit = startIndex + size / 2;
for (int i = startIndex; i < limit; i++) {
// swap(array, i, startIndex + (size - 1 - (i - startIndex)));
swap(array, i, 2 * startIndex + size - 1 - i);
}
}
private static void printSequence(int[] sequence) {
for (int i = 0; i < sequence.length; i++) {
System.out.printf("%d, ", sequence[i]);
}
System.out.println();
}
/**
* Implements the Knuth's L-Algorithm permutation algorithm
* modifying the collection in place
*/
private static void permutations(int[] sequence) {
final int N = sequence.length;
// There are n! permutations, but the first permutation is the array without
// modifications, so the number of permutations is n! - 1
int numPermutations = factorial(N) - 1;
// For every possible permutation
for (int n = 0; n < numPermutations; n++) {
// Iterate the array from right to left in search
// of the first couple of elements that are in ascending order
for (int i = N - 1; i >= 1; i--) {
// If the elements i and i - 1 are in ascending order
if (sequence[i - 1] < sequence[i]) {
// Then the index "i - 1" becomes our pivot index
int pivotIndex = i - 1;
// Scan the elements at the right of the pivot (again, from right to left)
// in search of the first element that is bigger
// than the pivot and, if found, swap it
for (int j = N - 1; j > pivotIndex; j--) {
if (sequence[j] > sequence[pivotIndex]) {
swap(sequence, j, pivotIndex);
break;
}
}
// Now reverse the elements from the right of the pivot index
// (this nice touch to the algorithm avoids the recursion)
reverse(sequence, pivotIndex + 1, N - 1);
break;
}
}
printSequence(sequence);
}
}
}
Решение @Filip Nyugen в JS для тех из вас, кто хочет получить ответ в JS
function printPermutationsIterative(string) {
const factorials = [];
factorials[0] = 1;
for (let i = 1; i <= string.length; i++) {
factorials[i] = factorials[i - 1] * i;
}
for (let i = 0; i < factorials[string.length]; i++) {
let onePermutation = "";
let temp = string;
let positionCode = i;
for (let position = string.length; position > 0; position--) {
let selected = positionCode / factorials[position - 1];
onePermutation += temp.charAt(selected);
positionCode = positionCode % factorials[position - 1];
temp = temp.substring(0, selected) + temp.substring(selected + 1);
}
console.log(onePermutation);
}
}
Это, конечно, делалось раньше, и одним из решений является Алгоритм перестановки Белла. Вы найдете решение здесь, где вы можете найти рекурсивное решение на Прологе и нерекурсивную перестановку колокола Алгоритм написан на Паскале.
Преобразование их в Java оставлено читателю в качестве упражнения.
Это простая функция Java для печати всех возможных перестановок (включая меньшие до пустой строки ""). если вам нужно распечатать только перестановки одинаковой длины, просто добавьте оператор if перед печатью.
Идея такая же, как рекурсия. Но вместо укладки вызовов методов. Мы используем структуру данных (как список в этом примере), чтобы сложить перестановки.
import java.util.LinkedList;
import java.util.List;
public class Permutations {
public void perm(String input) {
List<String[]> buffer = new LinkedList<>();
buffer.add(new String[]{input, ""});
while (!buffer.isEmpty()) {
String[] perm = buffer.remove(0);
System.out.println(perm[1]);
for (int i = 0; i < perm[0].length(); i++) {
buffer.add(new String[]{perm[0].substring(0, i) + perm[0].substring(i + 1), perm[1] + perm[0].charAt(i)});
}
}
}
}
