Generating combinations without recursion

Question

Given a list of strings and a length, give all combinations of that list with the given length. The problem is: your code must not be recursive. Yes, it can be done. I have done it myself, when I had no clue what this "recursion" was.

Input: A list of strings of an undefined length, and an integer defining the length of the combination. The strings will be at least one character long, and will only contain letters or numbers. The way of input will be specified by you, the programmer.

Output: A list of possible combinations as strings, not necessarily distinct (although you can make it that way, if you like). You do not have to sort the list.

Test Cases: As said before, the method of input will be specified by you.
[a,b] 3 -> Nothing
[1,0,0] 2 -> 10 10 00, or 00 10 if distinct.
[abc,bcd,cde] 2 -> abcbcd abccde bcdcde

If you even manage to do this, I will commend you. As always, shortest code wins. Good luck.

Answer 1

GolfScript (44 42 32 chars)

n%){\,=}+[[]]@1/{`{1$+}+%}%;\,n*

This takes input on stdin as a list of newline-separated strings followed by a line containing the desired subset size. It assumes that none of the input strings is empty. It takes some inspiration from Howard's solution, and can be shortened by two chars if using his input format:

~{\,=}+[[]]@1/{`{1$+}+%}%;\,n*

Output is a newline separated list of concatenations.

E.g.

$ golfscript.rb subcombo.gs <<END
> a
> b
> c
> 2
> END
ab
ac
bc

Note: this uses a horribly inefficient algorithm. A much nicer implementation in terms of performance is (62 61 chars)

n%)~\:S;2\?({2S,?<}{:s.~)&.s+.s^@4*/|}/{:x;S{;x.2/:x;1&},}%n*

which uses Gosper's hack.

Answer 2

GolfScript, 33 35 34 characters

~[[]]@{\{.[2$]+.,4$={puts}*}%\}%];

Assumes that the input is list of strings and number in GolfScript compatible format (on STDIN). Example:

> ["abc" "bcd" "cde"] 2
abcbcd
bcdcde
abccde

You can also test this version online.

Edit: The first version was broken.

Answer 3

Mathematica, 21

""<>##&@@@Subsets@##&

Usage:

""<>##&@@@Subsets@##&[{"a", "b", "c", "d"}, {3}]

{"abc", "abd", "acd", "bcd"}

Answer 4

Mathematica, 34 30 24 characters

StringJoin@@@Subsets@@#&

where i is input consisting of a list of the strings and the length of combinations. For example,

k = {{"abc", "bcd", "cde"},{2}};
StringJoin@@@Subsets@@#&[k]

(* out *)
{"abcbcd", "abccde", "bcdcde"}

---

Additional examples:

d = {"a", "b", "cd", "e", "fgh"}
m = {d, {2}}
n = {d, {3}}
p = {d, {4}}

StringJoin@@@Subsets@@#&[m]
StringJoin@@@Subsets@@#&[n]
StringJoin@@@Subsets@@#&[p]
(* out *)
{"ab", "acd", "ae", "afgh", "bcd", "be", "bfgh", "cde", "cdfgh", "efgh"}
{"abcd", "abe", "abfgh", "acde", "acdfgh", "aefgh", "bcde", "bcdfgh", "befgh", "cdefgh"}
{"abcde", "abcdfgh", "abefgh", "acdefgh", "bcdefgh"}

Answer 5

J, 50 48 46 44 43 41 35 characters

;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1

Takes input from the keyboard. I've changed the input format from previous answers. Strings should come first, single-quoted, and separated by semi-colons, followed by the integer.

   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
'hello';'mr';'wibble';2
hellomr
hellowibble
mrhello
mrwibble
wibblehello
wibblemr

Entering a number larger than the largest possible combination just gives the largest possible combination:

   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
hello mr wibble 8
hellomrwibble
hellowibblemr
mrhellowibble
mrwibblehello
wibblehellomr
wibblemrhello

Answer 6

Scala 52

Not a challenge - know your API:

def c(l:Seq[_],n:Int)=l combinations n mkString "\n"

invocation sample:

scala> c(Seq("foo", "bar", "foobar"), 2)
res199: String = 
List(foo, bar)
List(foo, foobar)
List(bar, foobar)

Now beary605 observes that he didn't thought about library methods combinations, so I come up with this one, which doesn't use combinations, but maybe he now will come up with a permutation prohibition.

Scala 63 (without literal combinations method):

def c(l:Seq[_],n:Int)=l.permutations.map(_.take(2).toSet).toSet

Answer 7

Java, 208 characters

No imports, two method calls, so it should be pretty guaranteed that there are no implisit recursive calls neither.

class S{public static void main(String[]a){int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;while(++i<1<<n)if(Integer.bitCount(i)==k){String s="";for(j=0;j<n;)if((i&1<<j++)!=0)s+=a[j];System.out.println(s);}}}

Slightly more readable:

class S{
    public static void main(String[]a){
        int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;
        while(++i<1<<n)
            if(Integer.bitCount(i)==k){
                String s="";
                for(j=0;j<n;)
                    if((i&1<<j++)!=0)
                        s+=a[j];
                System.out.println(s);
            }
    }
}

Takes input from command line arguments. First arg is the length and the rest is the strings. Outputs each combination on a separate line:

$ java S 3 A B C D
ABC
ABD
ACD
BCD