# 计算排列的最佳方法

go评论82阅读模式

Best way of calculating permutations

# 问题

I'm trying to figure out the best way of finding/automating all the possible permutations for a certain scenario.

I have a program which takes in a set of numbers [X, Y , Z], Each number has a predefined uncertainty. Therefore, I want to run my program against [X, Y , Z], [X+e, Y, Z] [x-e, Y, Z], [X, Y+e, Z] etc. Right now I have built an object which contains all the 27 possibilities and I'm iterating through it in order to provide my program with a new set of input. (I'll run my program 27 times with different set of inputs)

as time goes, I'd need to update my program to take in a bigger set of numbers. So I'm wondering whether there is a better way of calculating all the possible permutations my base set may have.

I'd rather know the way of implementing this instead of using any existing libraries (if there is any). I see this as a learning program. Thanks!

# 答案1

``````double[] numbers = new double[3];
double[] e = {-1e-6, 0, 1e-6};

for (double eX : e) {
for (double eY : e) {
for (double eZ : e) {
double[] newNumbers = {numbers[0] + eX, numbers[1] + eY, numbers[2] + eZ};
// 使用&quot;newNumbers&quot;运行您的程序。只是一个示例：
System.out.println(Arrays.toString(newNumbers));
}
}
}
``````

> 随着时间的推移，我需要更新我的程序以接受更大的数字集

Instead of writing down the the 3x3x3 sets of 3 numbers by hand, you can use nested loops. If you have 3 loops, one inside the other, each running 3 times, you get 27 outputs:

``````    double[] numbers = new double[3];
double[] e = {-1e-6, 0, 1e-6};

for (double eX : e) {
for (double eY : e) {
for (double eZ : e) {
double[] newNumbers = {numbers[0] + eX, numbers[1] + eY, numbers[2] + eZ};
// Run your program using &quot;newNumbers&quot;. Just as an example:
System.out.println(Arrays.toString(newNumbers));
}
}
}
``````

As for

> as time goes, I'd need to update my program to take in a bigger set of numbers

If the size of the set is going to be small and fixed, you can just add more nested loops. If not, you are going to need more advanced techniques .

# 答案2

``````public static void generate(int n, int[] a) {
if (n == 1) {
System.out.println(Arrays.toString(a));
} else {
for (int i = 0; i < n - 1; i++) {
generate(n - 1, a);
if ((n & 1) == 0) {
swap(i, n - 1, a);
} else {
swap(0, n - 1, a);
}
}
generate(n - 1, a);
}
}

public static void swap(int a, int b, int[] array) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
``````

Here is a permutation method I found some time ago. It prints them within the method. It only does single dimension permutations but you may be able to adapt it to your needs.

``````	public static void generate(int n, int[] a) {
if (n == 1) {
System.out.println(Arrays.toString(a));
} else {
for (int i = 0; i &lt; n - 1; i++) {
generate(n - 1, a);
if ((n &amp; 1) == 0) {
swap(i, n - 1, a);
} else {
swap(0, n - 1, a);
}
}
generate(n - 1, a);
}
}

public static void swap(int a, int b, int[] array) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}

</details>

# 答案3
**得分**: 1

```java
public interface Combinations<T> extends Stream<List<T>> {
public static <T> Stream<List<T>> of(Collection<T> collection) {
SpliteratorSupplier<T> supplier =
new SpliteratorSupplier<T>(collection);

return supplier.stream();
}
...
}
``````

``````Combinations.of(List.of(X, Y, Z)).forEach(t -> process(t));
``````

``````private Iterator<Supplier<Spliterator<T>>> spliterators = null;
private Spliterator<T> spliterator = Spliterators.emptySpliterator();
...
protected abstract Iterator<Supplier<Spliterator<T>>> spliterators();
...
@Override
public Spliterator<T> trySplit() {
if (spliterators == null) {
spliterators = Spliterators.iterator(spliterators());
}

return spliterators.hasNext() ? spliterators.next().get() : null;
}

@Override
public boolean tryAdvance(Consumer<? super T> consumer) {
boolean accepted = false;

while (!accepted) {
if (spliterator == null) {
spliterator = trySplit();
}

if (spliterator != null) {

if (!accepted) {
spliterator = null;
}
} else {
break;
}
}

return accepted;
}
``````

``````private class ForPrefix extends DispatchSpliterator<List<T>> {
private final int size;
private final List<T> prefix;
private final List<T> remaining;

public ForPrefix(int size, List<T> prefix, List<T> remaining) {
super(binomial(remaining.size(), size),
SpliteratorSupplier.this.characteristics());

this.size = size;
this.prefix = requireNonNull(prefix);
this.remaining = requireNonNull(remaining);
}

@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>();

if (prefix.size() < size) {
for (int i = 0, n = remaining.size(); i < n; i += 1) {
List<T> prefix = new LinkedList<>(this.prefix);
List<T> remaining = new LinkedList<>(this.remaining);

list.add(() -> new ForPrefix(size, prefix, remaining));
}
} else if (prefix.size() == size) {
list.add(() -> new ForCombination(prefix));
} else {
throw new IllegalStateException();
}

return list.iterator();
}
}
``````

``````private class ForCombination extends DispatchSpliterator<List<T>> {
private final List<T> combination;

public ForCombination(List<T> combination) {
super(1, SpliteratorSupplier.this.characteristics());

this.combination = requireNonNull(combination);
}

@Override
protected Iterator<Supplier<Spliterator<List<T>>>> spliterators() {
Supplier<Spliterator<List<T>>> supplier =
() -> Collections.singleton(combination).spliterator();

return Collections.singleton(supplier).iterator();
}
}
``````

I believe the best way to do this is to implement a `Spliterator` and wrap it in a `Stream`:

``````public interface Combinations&lt;T&gt; extends Stream&lt;List&lt;T&gt;&gt; {
public static &lt;T&gt; Stream&lt;List&lt;T&gt;&gt; of(Collection&lt;T&gt; collection) {
SpliteratorSupplier&lt;T&gt; supplier =
new SpliteratorSupplier&lt;T&gt;(collection);

return supplier.stream();
}
...
}
``````

Which solves the general use-case:

``````Combinations.of(List.of(X, Y, Z)).forEach(t -&gt; process(t));
``````

Implementing the `Spliterator` is straightforward but tedious and I have written about it here. The key components are a `DispatchSpliterator`:

``````private Iterator&lt;Supplier&lt;Spliterator&lt;T&gt;&gt;&gt; spliterators = null;
private Spliterator&lt;T&gt; spliterator = Spliterators.emptySpliterator();
...
protected abstract Iterator&lt;Supplier&lt;Spliterator&lt;T&gt;&gt;&gt; spliterators();
...
@Override
public Spliterator&lt;T&gt; trySplit() {
if (spliterators == null) {
spliterators = Spliterators.iterator(spliterators());
}

return spliterators.hasNext() ? spliterators.next().get() : null;
}

@Override
public boolean tryAdvance(Consumer&lt;? super T&gt; consumer) {
boolean accepted = false;

while (! accepted) {
if (spliterator == null) {
spliterator = trySplit();
}

if (spliterator != null) {

if (! accepted) {
spliterator = null;
}
} else {
break;
}
}

return accepted;
}
``````

A `Spliterator` for each prefix:

``````private class ForPrefix extends DispatchSpliterator&lt;List&lt;T&gt;&gt; {
private final int size;
private final List&lt;T&gt; prefix;
private final List&lt;T&gt; remaining;

public ForPrefix(int size, List&lt;T&gt; prefix, List&lt;T&gt; remaining) {
super(binomial(remaining.size(), size),
SpliteratorSupplier.this.characteristics());

this.size = size;
this.prefix = requireNonNull(prefix);
this.remaining = requireNonNull(remaining);
}

@Override
protected Iterator&lt;Supplier&lt;Spliterator&lt;List&lt;T&gt;&gt;&gt;&gt; spliterators() {
List&lt;Supplier&lt;Spliterator&lt;List&lt;T&gt;&gt;&gt;&gt; list = new LinkedList&lt;&gt;();

if (prefix.size() &lt; size) {
for (int i = 0, n = remaining.size(); i &lt; n; i += 1) {
List&lt;T&gt; prefix = new LinkedList&lt;&gt;(this.prefix);
List&lt;T&gt; remaining = new LinkedList&lt;&gt;(this.remaining);

list.add(() -&gt; new ForPrefix(size, prefix, remaining));
}
} else if (prefix.size() == size) {
list.add(() -&gt; new ForCombination(prefix));
} else {
throw new IllegalStateException();
}

return list.iterator();
}
}
``````

and one for each combination:

``````private class ForCombination extends DispatchSpliterator&lt;List&lt;T&gt;&gt; {
private final List&lt;T&gt; combination;

public ForCombination(List&lt;T&gt; combination) {
super(1, SpliteratorSupplier.this.characteristics());

this.combination = requireNonNull(combination);
}

@Override
protected Iterator&lt;Supplier&lt;Spliterator&lt;List&lt;T&gt;&gt;&gt;&gt; spliterators() {
Supplier&lt;Spliterator&lt;List&lt;T&gt;&gt;&gt; supplier =
() -&gt; Collections.singleton(combination).spliterator();

return Collections.singleton(supplier).iterator();
}
}
``````

• 本文由 发表于 2020年7月29日 23:48:18
• 转载请务必保留本文链接：https://go.coder-hub.com/63157442.html
• java
• permutation

go 44

go 46

go 46

go 50