N-ые комбинации ({a, b} = {b, a}) без повторения (перечисление/перебор)

Question

Я ищу алгоритм, который генерирует n-ые комбинации без повторения.

Я мог бы найти много на перестановках, где (a, b) != (b, a), но я ищу комбинации, где {a, b} = {b, a}.

Пример:

Set = {a, b, c} 
n = 2 
Combinations: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} 

Родовой, рекурсивная реализация в Java, который принимает набор или список будет большим. Я также хотел бы получить ссылку на хорошее объяснение, псевдо или пример кода.

Answer 1

Вы можете сделать это с помощью следующего рекурсивного метода:

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k) { 
    return getPermutations (elements,k,0); 
} 

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k, int i) { 
    ArrayList<ArrayList<T>> results = new ArrayList<>(); 
    if(k > 0) { 
     int n = elements.size(); 
     for(int j = i; j <= n-k; j++) { 
      T val = elements.get(j); 
      ArrayList<ArrayList<T>> tails = getPermutations(elements,k-1,j+1); 
      for(ArrayList<T> tail : tails) { 
       ArrayList<T> result = new ArrayList<>(); 
       result.add(val); 
       result.addAll(tail); 
       results.add(result); 
      } 
     } 
    } else { 
     results.add(new ArrayList<T>()); 
    } 
    return results; 
} 

You может затем запустить его, например, с помощью (jDoodle):

который генерирует:

[a, b] 
[a, c] 
[b, c] 
---------- 
[a, b, c] 
---------- 
[a, b] 
[a, c] 
[a, d] 
[b, c] 
[b, d] 
[c, d] 
---------- 
[a, b, c] 
[a, b, d] 
[a, c, d] 
[b, c, d] 

---

Программа работает следующим образом: k это число элементов, которые мы еще должны выбрать, и i текущее значение смещения. Первоначально это значение смещения равно 0.

Теперь мы итерации от i до n-k, ища потенциальных кандидатов, чтобы быть частью головы. Каждый элемент в этом диапазоне будет головкой для некоторых комбинаций. Мы выполняем рекурсию в остальной части списка. Рекурсия генерирует все списки, которые принимают k-1 элементов в остальной части списка. Тогда наша задача - просто добавить голову вперед и вернуть список.

Вы можете реализовать это как более оперативно, так и более консервативно, используя специальную форму LinkedList s (которые являются общими для логических и функциональных языков программирования).

Answer 2

Рекурсивный алгоритм прост:

1. Удалить первый элемент.
2. пара его с каждым другим элементом в списке
3. Добавить этот список в список, созданный остальными элементами

Answer 3

Вы помните, как найти работу k-th permutations of the elements? Не многие знают причину алгоритма, но за этим стоит математическая теория. Его можно решить, представив номер в factorial number system.

Почему я говорю о к-е перестановки, если речь шла о поиске к-ю комбинации? Только потому, что его можно решить с помощью подобной математической теории. Сюрприз, сюрприз, есть combinatorial number system:

К-комбинация множества S является подмножеством S с к (разных) элементов.Основная цель системы комбинаторных чисел - , обеспечивающая представление по каждому номеру всех {\ displaystyle {\ tbinom {n} {k}}} возможных k-комбинаций набора S из n элементов ,

Прочитайте статью и, скорее всего, вы сможете решить вашу проблему.

Answer 4

Учитывая вход list и n, расколоть list в первый элемент, а остальная часть списка, называя их head и tail. Затем комбинации вы стремитесь являются:

• комбинации вы можете получить от tail и n, плюс
• комбинации вы можете получить от tail и n-1, каждый с head предваряется

Если n равен 0, результатом является только одна комбинация: {}

Если n больше, чем размер list, результат нет комбинации

---

Side Примечание: Для получения удовольствия, я решил это в Haskell, положив n = 0 случай на вершине:

comb 0 _ = [[]] 
comb n (head:tail) | n > 0 = comb n tail ++ map (head:) (comb (n-1) tail) 
comb _ _ = []