3
\$\begingroup\$

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.

\$\endgroup\$

closed as unclear what you're asking by Wheat Wizard, Rɪᴋᴇʀ, mbomb007, Laikoni, Stephen Jan 5 at 15:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.

\$\endgroup\$
  • \$\begingroup\$ How do you even stumble across such obscure programming nuggets? \$\endgroup\$ – Gareth Jun 16 '12 at 11:16
  • \$\begingroup\$ @Gareth, I was taught this one by Arthur Norman. It's part of a collection of interesting titbits called HAKMEM. \$\endgroup\$ – Peter Taylor Jun 16 '12 at 19:11
  • \$\begingroup\$ Answer to you! You are pretty much the only answerer, other than the other GolfScript, that didn't use a built-in combo generator. \$\endgroup\$ – beary605 Jun 19 '12 at 2:03
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ puts? Seriously? \$\endgroup\$ – Peter Taylor Jun 17 '12 at 21:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Jun 18 '12 at 5:09
  • \$\begingroup\$ 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* \$\endgroup\$ – Peter Taylor Jun 18 '12 at 6:28
4
\$\begingroup\$

Mathematica, 21

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

Usage:

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

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

\$\endgroup\$
  • \$\begingroup\$ My goodness, that's really compact. \$\endgroup\$ – DavidC Jul 26 '12 at 17:00
3
\$\begingroup\$

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"}
\$\endgroup\$
  • 1
    \$\begingroup\$ Ha! Mma beating golfscript and J ... :D \$\endgroup\$ – Dr. belisarius Jun 19 '12 at 0:44
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Hehe, I should have added "no using built-in combo functions", but oh well. \$\endgroup\$ – beary605 Jun 18 '12 at 5:13
  • \$\begingroup\$ @beary605: Posted an alternative solution. Now you prohibit permutation, :) then map, then println? \$\endgroup\$ – user unknown Jun 19 '12 at 1:48
  • \$\begingroup\$ Hahaha. Very clever. ;) \$\endgroup\$ – beary605 Jun 19 '12 at 2:03
1
\$\begingroup\$

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
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.