返回列表列表的叉积

小编典典

返回列表列表的叉积

algorithm

给定一个大小为n的列表，编写一个程序以返回每个列表中包含的所有可能的元素组合。

例：

列表A =“ x，z”
列表B =“ a，b，c”
列表C =“ o，p”

输出：

ao
xap
bo
xbp
.....
zcp

顺序无关紧要，但是困难的部分是：您不能使用递归。我的解决方案：

void combos(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

如您所见，只有在我事先知道列表数量的情况下，它才有效。我很好奇递归是否是解决它的唯一方法。

阅读 321

2020-07-28

共1个答案

小编典典

就像将数字递增一样，例如以3为底的数字：

现在，将每个数字视为每个嵌套列表的索引。您将拥有与嵌套列表一样多的数字，即外部列表的大小。

每个数字的“基数”可能不同，并且是相应嵌套列表的大小。如果嵌套列表很大，则“数字”可以是非常大的数字。

因此，您首先创建“数字”或索引值的列表，然后将它们初始化为0。然后，您可以在这些索引处打印元素的值。然后，您增加最后一个索引值，根据需要进行滚动，就像正常数字一样，在第一个索引值滚动时停止。

这是使用数组数组（即）的Java实现String[][]。您可以根据需要轻松更改为List<List<String>>或List<String[]>。

@SafeVarargs
public static void printCombos(String[] ... lists) {
    if (lists.length == 0)
        throw new IllegalArgumentException("No lists given");
    for (String[] list : lists)
        if (list.length == 0)
            throw new IllegalArgumentException("List is empty");

    int[] idx = new int[lists.length];
    for (;;) {
        // Print combo
        for (int i = 0; i < lists.length; i++) {
            if (i != 0)
                System.out.print(' ');
            System.out.print(lists[i][idx[i]]);
        }
        System.out.println();

        // Advance to next combination
        for (int i = lists.length - 1; ++idx[i] == lists[i].length; ) {
            idx[i] = 0;
            if (--i < 0)
                return; // We're done
        }
    }
}

public static void main(String[] args) {
    String[][] data = { { "x", "z" }, { "a", "b", "c" }, { "o", "p" } };
    printCombos(data);
}

输出值

x a o
x a p
x b o
x b p
x c o
x c p
z a o
z a p
z b o
z b p
z c o
z c p

如果您使用列表而不是数组，那么代码将使用get(int)，这可能并不总是对性能有好处，例如for LinkedList。

如果是这种情况，请用替换int[] idx，使用Iterator[]对应列表的迭代器初始化每个数组条目。然后，通过Iterator从相关列表中检索新的数字，将“数字”重置为0 。

在这种情况下，它们甚至不必是列表，而可以是任何种类的集合，或更具体地说是Iterable对象。

2020-07-28