2

我想弄清楚的是一种算法，它可以创建可能的对，而不管在一组不确定的值中的顺序如何。

例如，假设集合是 A,B,C,D,E

那么可能的集合是

AB AC AD AE BC CD DE

但是...我也想要超过 2 个值的对。

例如

ABC ABD ABE BCD BCE

还有 ABCD 或 ABCE。这里的问题是我想创建一个方法，输入一个字符串数组 STring[]，输出将是一对 2,3.... 的字符串列表，最多值-1。

如果有人有解决方案的想法，请提供帮助。:)

4

4 回答 4

5

看来您想构建一个幂集。这个问题本质上是一样的，在那里寻找答案。

于 2009-06-09T18:11:30.953 回答
0

这是您可以做的计算量最大的事情之一。即使是远程大型数据集，这也无法很好地扩展。

对于不定集来说真的不实用。您可以限制可以生成的对，从而使这个比例更好。

于 2009-06-09T18:07:15.687 回答
0

您要创建的是输入排列的某种幂集。

Java 的迭代器概念理论上允许无限序列。

但是您的问题与比较有什么关系？

于 2009-06-09T18:13:27.817 回答
0

不是最有效的，而是一个解决方案：

import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class PowersetTest {

public static void main(String [] args){
    Set<Set<String>> sets =  permute(Arrays.asList("a","b","c","d","e"));
    for (Set<String> item : sets){
        System.out.printf("Set: %s%n", item.toString());
    }
}
    static public <T> Set<Set<T>> permute (Collection<T> items){
      Set<Set<T>> result = new HashSet<Set<T>>();
      for (final T item : items){
        Set<T> subsetElements = filter(items, new Predicate<T>(){public boolean apply(T f){ return (f!=item);}});
        if (subsetElements.size() > 0) {
          result.addAll(permute(subsetElements));
        }
        Set<T> temp = new HashSet<T>();
        temp.addAll(items);
        result.add(temp);
      }
      return result;
    }

  static public <T> Set<T> filter(Collection<T> items, Predicate<T> filter){ 
    Set<T> result = new HashSet<T>();
    for (T item : items){ 
      if (filter.apply(item)) {
        result.add(item);
      }
    }
    return result;
  }

  public interface Predicate<T>{ public boolean apply(T item); }
}
于 2009-06-09T19:05:28.717 回答