如何生成单词列表的所有唯一组合？

Question

我有一个单词列表,如:

List={"word1", "word2", "word3", ....}

如何生成这两个单词的所有独特组合的"双字长度"列表？

例如,如果上面的列表只包含三个单词,那么输出可能如下:

word1 word2
word1 word3
word2 word1
word2 word4
word3 word1
word3 word2

另外,请注意与... "word1 word2"不一样"word2 word1".

我知道这样一个最简单的解决方案:

for i=1 to N
  for j=1 to N
    if(i!=j) then
      print List[i]+" "+List[j]

但这有O(n ²)的复杂性.那么,实现相同的最差情况复杂度的最佳算法是什么.

Answer 1

算法的输出包含O(n^2)元素.由于每个输出元素都需要注意,因此您不可能希望实现比O(n^2)时间复杂度更好的方法.