Как сформировать все уникальные комбинации из списка слов?

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) сложность времени.