给定一个可变维度的数组...... 例如。数组={1,2,4,5}
我需要一种方法来概括数组的所有可能组合和子集。
给定一个包含 n 个元素的数组,我需要拥有所有子集(1 个元素的所有子集、2 个元素的所有子集、n 个元素的所有子集)以及每个子集的所有可能排列。
例如结果应该是:
{1}
{2}
{4}
{5}
{1,2}
{1,4}
{1,5}
{2,1}
{2,4}
{2,5}
....
....
{1,2,4,5}
{1,2,5,4}
{1,4,2,5}
{1,5,2,4}
{1,5,4,2}
{2,1,4,5}
{2,1,5,4}
....
....
{5,1,4,2}
{5,1,2,4}
{5,2,4,1}
....
....
etc...
所有组合!
有什么快速的方法吗? 我不知道....
最佳答案
您应该执行 2 个步骤:
- 您需要找到给定输入的所有子集。这组子集称为 Power Set .
- 对于这个幂集的每个元素(即每个子集),您需要所有 Permutations .
此实现使用 combinatorics 中的一些实用程序类项目。输出还包含空集 {}
,并且不按大小排序,但这可以作为后处理步骤轻松完成。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class AllCombinations {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1,2,4,5);
PowerSetIterable<Integer> powerSet =
new PowerSetIterable<Integer>(list);
for (List<Integer> subset : powerSet)
{
PermutationIterable<Integer> permutations =
new PermutationIterable<Integer>(subset);
for (List<Integer> permutation : permutations) {
System.out.println(permutation);
}
}
}
}
//From https://github.com/javagl/Combinatorics
class PowerSetIterable<T> implements Iterable<List<T>> {
private final List<T> input;
private final int numElements;
public PowerSetIterable(List<T> input) {
this.input = input;
numElements = 1 << input.size();
}
@Override
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
private int current = 0;
@Override
public boolean hasNext() {
return current < numElements;
}
@Override
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
List<T> element = new ArrayList<T>();
for (int i = 0; i < input.size(); i++) {
long b = 1 << i;
if ((current & b) != 0) {
element.add(input.get(i));
}
}
current++;
return element;
}
@Override
public void remove() {
throw new UnsupportedOperationException(
"May not remove elements from a power set");
}
};
}
}
//From https://github.com/javagl/Combinatorics
class PermutationIterable<T> implements Iterable<List<T>> {
public static int factorial(int n) {
int f = 1;
for (int i = 2; i <= n; i++) {
f = f * i;
}
return f;
}
private final List<T> input;
private final int numPermutations;
public PermutationIterable(List<T> input) {
this.input = input;
numPermutations = factorial(input.size());
}
@Override
public Iterator<List<T>> iterator() {
if (input.size() == 0) {
return Collections.<List<T>> singletonList(
Collections.<T> emptyList()).iterator();
}
return new Iterator<List<T>>() {
private int current = 0;
@Override
public boolean hasNext() {
return current < numPermutations;
}
@Override
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
// Adapted from http://en.wikipedia.org/wiki/Permutation
List<T> result = new ArrayList<T>(input);
int factorial = numPermutations / input.size();
for (int i = 0; i < result.size() - 1; i++) {
int tempIndex = (current / factorial) % (result.size() - i);
T temp = result.get(i + tempIndex);
for (int j = i + tempIndex; j > i; j--) {
result.set(j, result.get(j - 1));
}
result.set(i, temp);
factorial /= (result.size() - (i + 1));
}
current++;
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException(
"May not remove elements from a permutation");
}
};
}
}
关于java - java中数组的所有可能的组合和子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25204938/