相关疑难解决方法(0)

这个问题经常以某种形式出现(例如,见此处或此处).所以我认为我会以一般形式呈现它,并提供一个可能供将来参考的答案.

给定任意数量n的可能不同大小的向量,生成一个n列矩阵,其行描述从这些向量中获取的元素的所有组合(笛卡尔积).

例如,

vectors = { [1 2], [3 6 9], [10 20] }

应该给

combs = [ 1     3    10
          1     3    20
          1     6    10
          1     6    20
          1     9    10
          1     9    20
          2     3    10
          2     3    20
          2     6    10
          2     6    20
          2     9    10
          2     9    20 ]

给定未知数量的列表,每个列表具有未知长度,我需要生成具有所有可能的唯一组合的单个列表.例如,给出以下列表:

X: [A, B, C] 
Y: [W, X, Y, Z]

然后我应该能够生成12种组合:

[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

如果添加了3个元素的第三个列表,我将有36个组合,依此类推.

关于如何用Java做到这一点的任何想法？
(伪代码也可以)

我想用Java 计算任意数量的非空集的笛卡尔积.

我写过那个迭代代码......

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {
    List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
    List<T> elements = new ArrayList<T>(list.size());
    List<Set<T>> toRet = new ArrayList<Set<T>>();
    for (int i = 0; i < list.size(); i++) {
        iterators.add(list.get(i).iterator());
        elements.add(iterators.get(i).next());
    }
    for (int j = 1; j >= 0;) {
        toRet.add(Sets.newHashSet(elements));
        for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {
            iterators.set(j, list.get(j).iterator());
            elements.set(j, iterators.get(j).next());
        }
        elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());
    }
    return toRet;
}

......但我发现它相当不优雅.有人有更好的,仍然是迭代的解决方案吗？使用一些奇妙的功能性方法的解决方案？否则......关于如何改进它的建议？错误？

有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法(假设有一个).我环顾四周,谷歌搜索了一下,但看不到任何明显的东西,所以我可能会遗漏一些东西.

foreach (int i in is) {
   foreach (int j in js) {
      //Pair i and j
   }
}

这是我在代码中所做的高度简化的版本.两个整数是查找键,用于检索一个/多个对象,两个查找中的所有对象一起组合成新对象.

在一个更大更复杂的系统中,这个小块代码成为一个主要的性能瓶颈,因为它在规模上运行的数据集.其中一些可能通过改进用于存储对象的数据结构和所涉及的查找来减轻,但我认为主要问题仍然是笛卡尔积本身的计算.

编辑

关于我对算法的具体用法的更多背景,看看是否有任何技巧可以用来回应Marc的评论.整个系统是一个SPARQL查询引擎,它处理多组Graph数据的SPARQL查询,SPARQL是一种基于模式的语言,因此每个查询都包含一系列与Graph匹配的模式.在两个后续模式没有公共变量(它们是不相交的)的情况下,有必要计算由两个模式产生的解的笛卡尔积,以获得整个查询的可能解的集合.可能存在任何数量的模式,我可能需要多次计算笛卡尔积,如果查询由一系列不相交的模式组成,则可能导致可能解决方案的相当指数级扩展.

从现有的答案不知何故,我怀疑是否有任何技巧可以应用

更新

所以我想我会发布我实施的内容的更新,以便最大限度地减少对笛卡尔积的需求,从而优化查询引擎.请注意,并不总是可以完全消除对产品的需求,但几乎总是可以进行优化,因此连接的两组的尺寸要小得多.

由于作为一组三元模式的每个BGP(基本图形模式)作为一个块执行(实质上),引擎可以自由地重新排序BGP中的模式以获得最佳性能.例如,考虑以下BGP:

?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .

按原样执行查询需要笛卡尔积,因为第一个模式的结果与第二个模式不相交,因此前两个模式的结果是其各自结果的笛卡尔积.这个结果将包含比我们实际需要的结果多得多的结果,因为第三个模式限制了第一个模式的可能结果,但我们直到之后才应用此限制.但如果我们这样重新排序:

?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .

我们仍然需要笛卡尔积来获得最终结果,因为第二和第三种模式仍然是不相交的,但通过重新排序我们限制第二种模式的结果大小意味着我们的笛卡尔积的大小将小得多.

我们还有一些其他的优化方法,但是我不打算在这里发布它们,因为它开始对SPARQL引擎内部进行相当详细的讨论.如果有人对更多细节感兴趣,请发表评论或发送推文@RobVesse

我有一个ArrayList [] myList,我正在尝试创建一个列表,列出数组中值的所有排列.

示例:(所有值均为字符串)

myList[0] = { "1", "5", "3", "9" };
myList[1] = { "2", "3" };
myList[2] = { "93" };

myList的计数可以变化,因此事先不知道它的长度.

我希望能够生成一个类似于以下所有排列的列表(但有一些额外的格式).

1 2 93
1 3 93
5 2 93
5 3 93
3 2 93
3 3 93
9 2 93
9 3 93

这是否理解我想要完成的事情？我似乎无法想出这样做的好方法,(如果有的话).

编辑:
我不确定递归是否会干扰我以自己的方式格式化输出的愿望.对不起我之前没有提到我的格式.

我想最终构建一个string []数组,其中包含如下格式的所有组合:

对于"1 2 93"排列

我希望输出为"val0 = 1; val1 = 2; val2 = 93;"

我现在将尝试递归.谢谢Dr.Jokepu

假设我有两组数字:

{1, 2, 3},
{4, 5}

我想创建一个输出以下6种组合的算法(在Java中):

1,4
1,5
2,4
2,5
3,4
3,5

每组中可以有任意数量的组和任意数量的成员.因此在上面的例子中,有2组,第一组有3个成员,第二组有2个成员.另一个例子如下(3组,第一组3名成员,第2组和第3组2名成员):

{1, 2, 3},
{4, 5},
{6, 7}

这将产生以下12种组合:

1,4,6
1,4,7
1,5,6
1,5,7

2,4,6
2,4,7
2,5,6
2,5,7

3,4,6
3,4,7
3,5,6
3,5,7

我怎么能用Java做到这一点？我正在尝试使用递归,我已经看了一个类似的问题,但我仍然很短.谢谢您的帮助!(PS这不是作业作业)

我有n套.每个集合都有不同数量的元素.我想写一个算法,它给出了所有可能的组合.例如:让我们说:

S1={1,2}, S2={A,B,C}, S3={$,%,£,!}

组合应该看起来像

C1={1,A,$}
C2={1,A,%}

....等等可能的组合数量 2*3*4 = 24

请帮我用Java编写这个算法.

提前谢谢了

我有一些ArrayList每个ArrayList都有对象,每个可以有不同的长度.我需要生成排列,如下例所示:

假设我有2个arraylist

arraylist A有对象a,对象b和对象c
arraylist B有对象d,对象e

那么输出应该是6个新的arraylist与这个组合:

组合1对象a和对象d,
组合2对象a和对象e,
组合3对象b和对象d,
组合4对象b和对象e,
组合5对象c和对象d,
组合6对象c和对象e,

谁能帮我？

有没有一种有效的方法来查找Java中多个枚举之间的所有可能组合？

考虑以下三个枚举 -

public enum EnumOne {
   One ("One"),
   OneMore ("OneMore");
}

public enum EnumTwo {
   Two ("Two"),
}

public enum EnumThree {
   Three ("Three"),
   ThreeMore ("ThreeMore");
}

我希望输出产生这些多个枚举之间的所有可能组合,即

{EnumOne.One, EnumTwo.Two, EnumThree.Three},
{EnumOne.One, EnumTwo.Two, EnumThree.ThreeMore},
{EnumOne.OneMore, EnumTwo.Two, EnumThree.Three},
{EnumOne.OneMore, EnumTwo.Two, EnumThree.ThreeMore}

希望找到一种有效的方法来处理它.

谢谢

我想找到一组元素的笛卡尔积.这是一个例子

example 1 :
sets :(ab) (bc) (ca)

笛卡儿的产品是,

abc aba acc aca bbc bba bcc bca

example 2 :
sets : (zyx) b c

笛卡儿的产品是,

zbc ybc xbc

所以我在想一个在java中执行的算法,它可以找到在开始编译时定义的特定数量的组的笛卡尔积.

我想从散列图中检索k,v对.这些托管是这样的:

a = 3,4 
b = 5,6

等等.我需要这些值的组合.

a=3, b=5. 
a=3, b=6.
a=4, b=5.
a=4, b=6.

我不知道有多少个键和多少个值.使用entryset我可以得到值而不是组合.它看起来像递归,但如何？

这是我的代码:

HashMap<String, String[]> map = new HashMap<String, String[]>();

BufferedReader file = new BufferedReader(new FileReader("test.txt"));
String str;


while ((str = file.readLine()) != null) { 


    ... logic


    map.put(key, value);



}
System.out.println("number of keys: " + map.size());
for(Entry<String, String[]> entry : map.entrySet()) {
    for(String value : entry.getValue()) {
        System.out.println(entry.getKey() + ": " + value);
    }
}
file.close();