# Generating combinations without recursion [closed]

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.

• what does "without recursion" mean in this context? can you use a while loop? for loop? context would be helpful here...
– Jeff
Jun 16, 2012 at 7:45
• If I look at your third test case, it seems that you care about the order. Is cdeabc a valid combination? Jun 16, 2012 at 8:45
• Yes it is. Why not? Jun 16, 2012 at 9:27
• @beary605 Because your test case says it is not. Jun 16, 2012 at 9:55
• Are we permitted to assume that none of the input strings are empty or contain newlines? Jun 16, 2012 at 10:01

## 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. • How do you even stumble across such obscure programming nuggets? Jun 16, 2012 at 11:16 • @Gareth, I was taught this one by Arthur Norman. It's part of a collection of interesting titbits called HAKMEM. Jun 16, 2012 at 19:11 • Answer to you! You are pretty much the only answerer, other than the other GolfScript, that didn't use a built-in combo generator. Jun 19, 2012 at 2:03 ### GolfScript, 3335 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. • puts? Seriously? Jun 17, 2012 at 21:35 • @PeterTaylor Maybe I don't understand you correctly, but why not? Btw I just noticed that we can save a char and get rid of the dot. Jun 18, 2012 at 5:09 • It's so long that I think its only purpose is debugging. You can save two more chars by ditching puts and just filtering the list to ones of the right length: ~[[]]@{\{.[2$]+}%\}%;{,1$=},\;n* Jun 18, 2012 at 6:28 ## Mathematica, 21 ""<>##&@@@Subsets@##&  Usage: ""<>##&@@@Subsets@##&[{"a", "b", "c", "d"}, {3}]  {"abc", "abd", "acd", "bcd"} • My goodness, that's really compact. Jul 26, 2012 at 17:00 ## 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"}  • Ha! Mma beating golfscript and J ... :D Jun 19, 2012 at 0:44 ## J, 504846444341 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  ### 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  • Hehe, I should have added "no using built-in combo functions", but oh well. Jun 18, 2012 at 5:13 • @beary605: Posted an alternative solution. Now you prohibit permutation, :) then map, then println? Jun 19, 2012 at 1:48 • Hahaha. Very clever. ;) Jun 19, 2012 at 2:03 # 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