英文:
Best way of calculating permutations
问题
我正在尝试找出一种在特定情境下找到/自动化所有可能排列的最佳方法。
我有一个程序，它接受一组数字[X, Y, Z]，每个数字都有预定义的不确定性。因此，我想运行我的程序对[X, Y, Z]、[X+e, Y, Z]、[X-e, Y, Z]、[X, Y+e, Z]等进行测试。目前我已经构建了一个包含所有27种可能性的对象，并正在遍历它，以便为我的程序提供新的输入集。 (我将以不同的输入集运行我的程序27次)
随着时间的推移，我需要更新我的程序以接受更大的数字集。所以我想知道是否有更好的方法来计算我的基本集可能具有的所有可能排列。
我宁愿知道如何实现这一点，而不是使用任何现有的库（如果有的话）。我把这看作是一个学习项目。谢谢！
英文:
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
得分: 1
不必手工书写3x3x3组的3个数字，可以使用嵌套循环。如果有3个循环，一个嵌套在另一个内部，每个循环运行3次，您将获得27个输出：
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};
// 使用"newNumbers"运行您的程序。只是一个示例：
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 "newNumbers". 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
得分: 1
这是我一段时间前找到的一个排列方法。它在方法内部打印排列结果。它只处理单维度的排列，但你可能可以根据自己的需求进行调整。
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 < 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;
}
</details>
# 答案3
**得分**: 1
我认为最好的方法是实现一个 [`Spliterator`](https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html) 并将其包装在一个 [`Stream`](https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html) 中：
```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));
实现 Spliterator 是直截了当但繁琐的，我在这里有写过。关键组件是 DispatchSpliterator：
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) {
accepted = spliterator.tryAdvance(consumer);
if (!accepted) {
spliterator = null;
}
} else {
break;
}
}
return accepted;
}
每个前缀的 Spliterator：
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);
prefix.add(remaining.remove(i));
list.add(() -> new ForPrefix(size, prefix, remaining));
}
} else if (prefix.size() == size) {
list.add(() -> new ForCombination(prefix));
} else {
throw new IllegalStateException();
}
return list.iterator();
}
}
以及每个组合的 Spliterator：
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<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();
}
...
}
Which solves the general use-case:
Combinations.of(List.of(X, Y, Z)).forEach(t -> process(t));
Implementing the Spliterator is straightforward but tedious and I have written about it here. The key components are a DispatchSpliterator:
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) {
accepted = spliterator.tryAdvance(consumer);
if (! accepted) {
spliterator = null;
}
} else {
break;
}
}
return accepted;
}
A Spliterator for each prefix:
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);
prefix.add(remaining.remove(i));
list.add(() -> new ForPrefix(size, prefix, remaining));
}
} else if (prefix.size() == size) {
list.add(() -> new ForCombination(prefix));
} else {
throw new IllegalStateException();
}
return list.iterator();
}
}
and one for each combination:
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();
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论