Алгоритмы - комбинации и перестановки

Question

Вопрос hwk и, видимо, также распространенный вопрос интервью, с которым у меня возникли проблемы:

" Напишите алгоритм (псевдокод), который распечатывает все подмножества трех элементов набора из n элементов. Элементы этого набора сохраняются в списке, который является входом для алгоритма. «

Так, например, если S = ​​{1,2,3,4}, алгоритм выведет эти четыре комбинации:

123 124 134 234

Может кто-нибудь предложить свои мысли / решение?

Answer 1

Рекурсивный:

def subset (prefix, list, count):
    if count is 0:
        print prefix
        return
    for each element in list:
        subset (prefix & element, list beyond element, count - 1)

subset ("", {1,2,3,4}, 3)

Python подтверждение концепции:

def subset (prefix, list, count):
    if count is 0:
        print prefix
        return
    for i in range (len(list)):
        subset ("%s%s"%(prefix,list[i]), list[i+1:], count - 1)

subset ("", "1234", 3)

, который выводит для различных значений входной строки (второй параметр subset):

123456   12345   1234   123   12
------   -----   ----   ---   --
123      123     123    123
124      124     124
125      125     134
126      134     234
134      135
135      145
136      234
145      235
146      245
156      345
234
235
236
245
246
256
345
346
356
456

Answer 2

Фасилий 2 Кнута из тома 4 имеет элегантное решение.

http://cs.utsa.edu/~wagner/knuth/

Редактировать: это брошюра 3А http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf

Answer 3

Думайте рекурсивно.Вы хотите подмножества длины 3. Что я могу сделать, так это то, что для всех n в подмножествах я просто прикреплю все подмножества длины 2 к n.При рассмотрении длины 2 я не буду рассматривать элементы от 1 до n, так как они уже обработаны.S (3, n) = nS (2, n + 1) для всех n;

например, когда n = 1, я создам все подмножества длины 2 с оставшимися элементами.(2,3), (3,4), (2,4).Теперь присоединяя 1, я получу (1,2,3), (1,3,4), (1,2,4).Я продолжу это для 2. Только для 2 при создании подмножеств длины 2 я не буду рассматривать 1. Таким образом, у меня есть только одно подмножество длины 2 (3,4).Присоединяя это к 2, я получаю (2,3,4) и объединяю все, что получаю (1,2,3), (1,3,4), (1,2,4), (2,3,4).

Answer 4

Сначала я попытался решить ее для конкретного случая, когда S = {1,2,3,4} и n = 3, но затем я решил просто сделать это для S = список из m элементов и n произвольногочисло> = 1.Кроме того, это моя первая программа на Java :), поэтому я надеюсь, вам понравится!

import java.util.Arrays;

public class Combinari {

    public static void combinari(int[] array, int n, int[] toPrint){
        if(n==1){
            for(int i=0;i<array.length;i++){
                for(int j=0;j<toPrint.length;j++) System.out.print(toPrint[j]);
                System.out.println(array[i]);
            }
        }
        else {
            for(int i=0;i<array.length-n+1;i++){
                int [] newToPrint = Arrays.copyOf(toPrint, toPrint.length+1);
                newToPrint[toPrint.length] = array[i];
                int [] new_array =  Arrays.copyOfRange(array, i+1, array.length);
                combinari(new_array,n-1,newToPrint);
            }
        }
    }



    public static void main(String[] args) {
        int [] array = {1,2,3,4,5,6,7};
        int [] iaka={}; // iaka est for printing :)
        combinari(array, 3, iaka);
        System.out.println("");

    }

}