数组的所有可能组合

arrays algorithm java

2022-09-01 22:48:58

我有一个字符串数组

{"ted", "williams", "golden", "voice", "radio"}

我想要这些关键字的所有可能组合，如下所示：

{"ted",
 "williams",
 "golden", 
 "voice", 
 "radio",
 "ted williams", 
 "ted golden", 
 "ted voice", 
 "ted radio", 
 "williams golden",
 "williams voice", 
 "williams radio", 
 "golden voice", 
 "golden radio", 
 "voice radio",
 "ted williams golden", 
 "ted williams voice", 
 "ted williams radio", 
 .... }

我已经花了几个小时没有有效的结果（高级编程的副作用？？）。

我知道解决方案应该是显而易见的，但老实说，我被困住了！接受 Java/C# 中的解决方案。

编辑：

这不是家庭作业
“ted williams”和“williams ted”被认为是一样的，所以我只想要“ted williams”

编辑2：在查看了答案中的链接后，事实证明，番石榴用户可以在com.google.common.collect.Sets中使用powerset方法。

答案 1

编辑：正如FearUs所指出的，更好的解决方案是使用Guava的Sets.powerset（Set set）。。

编辑2：更新的链接。

此解决方案的快速和肮脏的翻译：

public static void main(String[] args) {

    List<List<String>> powerSet = new LinkedList<List<String>>();

    for (int i = 1; i <= args.length; i++)
        powerSet.addAll(combination(Arrays.asList(args), i));

    System.out.println(powerSet);
}

public static <T> List<List<T>> combination(List<T> values, int size) {

    if (0 == size) {
        return Collections.singletonList(Collections.<T> emptyList());
    }

    if (values.isEmpty()) {
        return Collections.emptyList();
    }

    List<List<T>> combination = new LinkedList<List<T>>();

    T actual = values.iterator().next();

    List<T> subSet = new LinkedList<T>(values);
    subSet.remove(actual);

    List<List<T>> subSetCombination = combination(subSet, size - 1);

    for (List<T> set : subSetCombination) {
        List<T> newSet = new LinkedList<T>(set);
        newSet.add(0, actual);
        combination.add(newSet);
    }

    combination.addAll(combination(subSet, size));

    return combination;
}

测试：

$ java PowerSet ted williams golden
[[ted], [williams], [golden], [ted, williams], [ted, golden], [williams, golden], [ted, williams, golden]]
$

答案 2

我刚刚面对这个问题，对StackExchange发布的答案并不满意，所以这是我的答案。这将返回对象数组中的所有组合。我会把它留给读者，以适应你正在使用的任何类（或使其通用）。Port

此版本不使用递归。

public static Port[][] combinations ( Port[] ports ) {
    
    List<Port[]> combinationList = new ArrayList<Port[]>();
    // Start i at 1, so that we do not include the empty set in the results
    for ( long i = 1; i < Math.pow(2, ports.length); i++ ) {
        List<Port> portList = new ArrayList<Port>();
        for ( int j = 0; j < ports.length; j++ ) {
            if ( (i & (long) Math.pow(2, j)) > 0 ) {
                // Include j in set
                portList.add(ports[j]);
            }
        }
        combinationList.add(portList.toArray(new Port[0]));
    }
    return combinationList.toArray(new Port[0][0]);
}

有关更优化的版本，请参阅此页面上的@Aison解决方案。