Algorithms - Combinations and Permutations

A hwk question and apparently also a common interview question I'm having trouble with:

"Write an algorithm (pseudocode) that prints out all the subsets of three elements of a set of n elements. The elements of this set are stored in a list that is the input to the algorithm."

So for example if S = {1,2,3,4} the algorithm would print out these four combinations:

123 124 134 234

Can anyone offer their thoughts / a开发者_开发百科 solution?

Recursively:

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)

A Python proof of concept:

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)

which outputs, for various values of the input string (second parameter to 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

Knuth's fascile 2 from volume 4 has an elegant solution.

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

Edit: it is fascicle 3A http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf

Think recursively. You want subsets of length 3. What I can do is that for all n in subsets I will simply attach all the subsets of length 2 to n. While considering the length 2 I will not consider any elements for 1 to n, as these are already processed. S(3,n) = n.S(2,n+1) for all n;

e.g. when n = 1, I will create all the subsets of length 2 with remaining elements. (2,3),(3,4),(2,4). Now attaching 1 I will get (1,2,3),(1,3,4),(1,2,4). I will continue this for 2. Only that for 2 while creating the subsets of length 2 I will not consider 1. So I have only one subset of length 2 (3,4). Attaching this to 2 I get (2,3,4) and combining all I get (1,2,3),(1,3,4),(1,2,4),(2,3,4).

I first tried to solve it for the specific case when S = {1,2,3,4} and n=3, but then I decided to just do it for S = a list of m elements and n an arbitrary number>=1. Also, this is my first program in Java :) so I hope u enjoy!

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("");

    }

}