# 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 '12 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 '12 at 8:45
• Yes it is. Why not? Jun 16 '12 at 9:27
• @beary605 Because your test case says it is not. Jun 16 '12 at 9:55
• Are we permitted to assume that none of the input strings are empty or contain newlines? Jun 16 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 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 '12 at 5:13 • @beary605: Posted an alternative solution. Now you prohibit permutation, :) then map, then println? Jun 19 '12 at 1:48 • Hahaha. Very clever. ;) Jun 19 '12 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