1

我有一个List<List<String>> 我需要在第一个维度上获取所有可能连接的列表

[ [1,2 ], [1] , [3,4] ]

应该给:

[ 113, 114, 213, 214 ]

我正在尝试 2 个循环,就像它应该可能的那样。

这是我尝试过的:

private static List<String> constructIndexes(List<List<String>> indexList){
    List<String> index = new ArrayList<String>();

    String v="";

    for (int i=0; i< indexList.size(); i++){
        List<String> l =  indexList.get(i);
        for (int j=0; j<l.size(); j++){
            if (index.size()>0){
                for (int k=0; k<index.size(); k++){
                    index.set(k, index.get(k)+l.get(j));
                    // System.out.println(">");
                }
            } else {
                index.add(l.get(j));
            }

        }
    }

    return index;
}

一些初始化代码:

List<List<String>> indexList = new ArrayList<List<String>>();

    List<String> l = new ArrayList<String>();
    l.add("1");
    l.add("2");
    indexList.add(l);
    l = new ArrayList<String>();
    l.add("1");
    indexList.add(l);
    l = new ArrayList<String>();
    l.add("3");
    l.add("4");
    indexList.add(l);

    System.out.println( constructIndexes(indexList));
4

3 回答 3

1

如何保留一些跟踪每个元素的索引的索引计数器,然后进行传统的向左进位,就像添加时一样,例如 9 + 1 = 10(向左进位,并设置 0)。

private static List<String> constructIndexes(List<List<String>> indexList) {
    List<String> index = new ArrayList<String>();
    int n = indexList.size();
    int[] counter = new int[n];
    int[] max = new int[n];
    int combinations = 1;
    for (int i = 0; i < n; i++) {
        max[i] = indexList.get(i).size();
        combinations *= max[i];
    }
    int nMinus1 = n - 1;
    for (int j = combinations; j > 0; j--) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            builder.append(indexList.get(i).get(counter[i]));
        }
        index.add(builder.toString());

        counter[nMinus1]++;
        for (int i = nMinus1; i >= 0; i--) {
            // overflow check
            if (counter[i] == max[i]) {
                if (i > 0) {
                    // carry to the left
                    counter[i] = 0;
                    counter[i - 1]++;
                }
            }
        }
    }
    return index;

测试

List<List<String>> test = Arrays.asList(Arrays.asList("1", "2"),
        Arrays.asList("1"), Arrays.asList("3", "4"));
System.out.println(constructIndexes(test));

输出

[113, 114, 213, 214]
于 2012-06-19T22:55:42.420 回答
0

由于外部列表(即列表列表)中的列表数量直到运行时才知道,因此您无法预先知道循环的数量。在这种情况下,您需要一个递归解决方案:

public static void combine(List<List<String>> data, int[] pos, int n, List<String> res) {
    if (n == pos.length) {
        StringBuilder b = new StringBuilder();
        for (int i = 0 ; i != pos.length ; i++) {
            b.append(data.get(i).get(pos[i]));
        }
        res.add(b.toString());
    } else {
        for (pos[n] = 0 ; pos[n] != data.get(n).size() ; pos[n]++) {
            combine(data, pos, n+1, res);
        }
    }
}

以下是如何调用它:

List<List<String>> indexList = new ArrayList<List<String>>();
List<String> a = new ArrayList<String>();
a.add("1");
a.add("2");
List<String> b = new ArrayList<String>();
b.add("1");
List<String> c = new ArrayList<String>();
c.add("3");
c.add("4");
indexList.add(a);
indexList.add(b);
indexList.add(c);
List<String> res = new ArrayList<String>();
combine(indexList, new int[indexList.size()], 0, res);
for (String s : res) {
    System.out.println(s);
}
于 2012-06-19T22:21:49.957 回答
0

这对你有用吗

 private <T> List<T> getNthCombination(List<List<T>> lists, int n) {

    List<T> nthCombination = new ArrayList<T>(lists.size());

    int nCarry = n;
    for (List<? extends T> list: lists) {
         int lSize = list.size();
         nthCombination.add(list.get(nCarry % lSize));
         nCarry /= lSize;
    }

    return nthCombination;
}

当然,这是一个基本的组合问题,并且有一些库可以处理这类问题。

于 2012-06-20T07:08:51.783 回答