Lojic Technologies

36 Responses

Subscribe to comments with RSS.

  1. Jordan L. contributed this Java version (I added class wrapper and normalized choice strings).

    import java.util.*;
    
    public class Choices {
      public static void choices(List<Object[]> choices, String sofar) {
        if (choices.isEmpty())
          System.out.println(sofar);
        else
          for (Object choice : choices.get(0))
            choices(choices.subList(1, choices.size()),
              sofar + choice.toString() + " ");
      }
    
      public static void main(String[] args) {
        choices(Arrays.asList(new Object[][] {
          { "small", "medium", "large" },
          { "vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger" },
          { "cup", "cone" } }), "");
      }
    }
    

    Brian Adkins

    August 31, 2007 at 9:21 pm

  2. Here’s a Scheme version from a friend in Ohio that I tweaked just a bit.

    (define (choices menu sofar)
      (cond
        [(null? menu)
          (for-each (lambda (word) (printf "~a " word)) sofar)
          (newline)]
        [else
          (for-each (lambda (item)
            (choices
              (cdr menu)
              (append sofar (list item)))) (car menu))]))
    
    (choices (list
      '(small medium large)
      '(vanilla "ultra chocolate" lychee "rum raisin" ginger)
      '(cone cup)) '())
    

    Brian Adkins

    September 1, 2007 at 1:29 pm

  3. Here’s a Common Lisp version, but I’m hoping some kind soul on comp.lang.lisp will provide me with pointers to make it cleaner. Especially with the print-choice function.

    (defun print-choice (lst)
      (dolist (i lst) (format t "~a " i))
      (format t "~%"))
    
    (defun choices (menu sofar)
      (if menu
        (dolist (i (car menu))
          (choices (cdr menu) (append sofar (list i))))
        (print-choice sofar)))
    
    (choices (list
      (list "small" "medium" "large")
      (list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
      (list "cone" "cup")) '())
    

    Brian Adkins

    September 1, 2007 at 3:58 pm

  4. PHP:

    function choices($menu, $sofar) {
        if (count($menu))
            foreach ($menu[0] as $item)
                choices(array_slice($menu,1), $sofar."$item ");
        else
            echo "$sofar\n";
    }
    choices(array(
        array("small","medium","large"),
        array("vanilla","ultra chocolate","lychee","rum rasin","ginger"),
        array("cone","cup")), "");
    

    Luke

    September 1, 2007 at 4:33 pm

  5. OK, here’s a C# version. No need for a namespace declaration if we’re OK running in the default namespace. No need for a using statement either, if you fully qualify your types.

    Chip H.

    class Program
    {
      static void Main(string[] args) {
        string[] sizes = new string[] { "small ", "medium ", "large " };
        string[] flavors = new string[] { "vanilla ", "ultra chocolate ", "lychee ", "rum raisin ", "ginger " };
        string[] servings = new string[] { "cone", "cup" };
    
        foreach (string size in sizes)
          foreach (string flavor in flavors)
            foreach (string serving in servings)
              System.Console.WriteLine(size + flavor + serving);
      }
    }
    

    Chip H.

    September 1, 2007 at 8:33 pm

  6. Since it would be trivial to translate the Ruby version directly to Python, I thought I’d approach the problem from a completely different angle. Here’s my 4-line Python version:

    optstr  = lambda x : (type(x)==str)*str(x)+(type(x)!=str)*' '.join(x)
    prod1   = lambda elem, vec : map(lambda x : optstr(elem)+' '+optstr(x), vec)
    xprod   = lambda vec1, vec2 : reduce(list.__add__,map(lambda elem : prod1(elem ,vec2), vec1))
    choices = lambda x : '\n'.join(reduce(xprod, x))
    
    q = [['small','medium','large'],
      ['vanilla', ['ultra', 'chocolate'], 'lychee', ['rum', 'raisin'], 'ginger'],
      ['cone', 'cup']]
    
    print choices(q)
    

    Scott Moonen

    September 1, 2007 at 9:09 pm

  7. Scott, extra points for creativity 🙂 Darn you for causing me to translate that back to other languages now…

    Brian Adkins

    September 1, 2007 at 9:27 pm

  8. Here’s a direct translation of Scott’s Python solution to Ruby. I had to write the reduce function because I wasn’t aware of any built-in Ruby function that was close.

    I like the Python lambda invocation better than having to say x.call() in Ruby.

    def reduce fn, lst
      return lst if lst.length < 2
      result = fn.call(lst[0],lst[1])
      return lst.length == 2 ? result : reduce(fn, [fn.call(lst[0],lst[1])] + lst[2..-1])
    end
    
    optstr  = lambda {|x| x.instance_of?(String) ? x : x.join(' ')}
    prod1   = lambda {|elem, vec| vec.map {|x| optstr.call(elem)+' '+optstr.call(x)}}
    xprod   = lambda {|vec1, vec2| reduce(lambda {|a, b| a+b}, vec1.map {|elem| prod1.call(elem, vec2)})}
    choices = lambda {|x| reduce(xprod, x).join("\n")}
    
    q = [ ['small','large'],
     ['vanilla', ['ultra', 'chocolate'], ['rum', 'raisin']],
     ['cone', 'cup'],
     [ 'here', 'to go'] ]
    
    puts choices.call(q)
    

    Brian Adkins

    September 1, 2007 at 11:34 pm

  9. My bad. Proc#[] is a synonym for Proc.call, so the following will work:

    choices[q]

    instead of:

    choices.call(q)

    I’m not sure it’s much of an improvement though, since it makes the function call look like an array reference! I think Scheme wins out here for consistency:

    (expr arg1 arg2 … )

    whatever expr evaluates to is executed as a function call:

    ((if ( 7

    Brian Adkins

    September 2, 2007 at 12:00 am

  10. Lisp translation of Scott’s Python translation of the Logo program 🙂

    Had to write a join-string function since I couldn’t find a Lisp equivalent of Ruby’s list.join(‘ ‘) or Python’s ‘ ‘.join(list)

    I’m very much a Lisp newbie, but I was surprised how straightforward the port went (except for getting stuck on join-string and having to research to find #Newline – argh). I’m curious, given a large set of algorithms, whether it would be easier to port Python/Ruby to Lisp or vice versa given equal language skills.

    ;; Helper function
    (defun join-string (sep lst)
      (if (cdr lst)
        (concatenate 'string (car lst) (string sep) (join-string sep (cdr lst)))
        (car lst)))
    
    (defun prod1 (elem vec)
      (mapcar #'(lambda (x) (join-string " " (list elem x))) vec))
    
    (defun xprod (vec1 vec2)
      (reduce
        #'(lambda (a b) (concatenate 'list a b))
        (mapcar #'(lambda (elem) (prod1 elem vec2)) vec1)))
    
    (defun choices (x)
      (join-string #\Newline (reduce #'xprod x)))
    
    (princ (choices (list (list "small" "large")
                (list "vanilla" "ultra chocolate")
                (list "cone" "cup")
                (list "to go" "eat in"))))
    

    Brian Adkins

    September 2, 2007 at 1:28 am

  11. My first instinct in python turns the cross product function inside out which may not optimize as well. Shame, because it feels a lot more readable to me.

    def cross(aa):
        if len(aa) == 0:
            return [()]
        else:
            return sum([[(x,) + y for x in aa[0]] for y in cross(aa[1:])], [])
    
    def choices(menu):
        return "\n".join(" ".join(x) for x in cross(menu))
    
    print choices([['small',  'medium',  'large'],
             ["vanilla","ultra chocolate","lychee","rum rasin","ginger"],
             ['cup', 'cone']])
    

    Ben Rogers

    September 2, 2007 at 10:47 am

  12. Wow. I asked for a translation of the Python code back to Logo, and Brian Harvey responded with this:

    to choices :menu
       foreach crossmap "sentence :menu "print
    end
    
    choices [[large medium small]
       [vanilla [ultra chocolate] lychee [rum raisin]]
       [cone cup]]
    

    Is that concise or what?! I was thinking of creating yet another web framework in Lisp, but maybe I should use Logo? 🙂

    http://groups.google.com/group/comp.lang.logo/browse_frm/thread/96b5071c0e06b5b8/#

    Brian Adkins

    September 2, 2007 at 3:08 pm

  13. Please forgive my amature Haskell. I don’t know whether there is a cross product function in one of its libraries, but writing one isn’t too hard.

    choices (xs:[]) = xs
    choices (xs:xss) = foldr ((++) . (\ys -> map (++ " " ++ ys) xs)) [] (choices xss)
    
    main = putStr (unlines(
           choices [["small",  "medium",  "large"],
                    ["vanilla","ultra chocolate","lychee","rum rasin","ginger"],
                    ["cup", "cone"]]
                          ))
    

    Note from Brian: this didn’t seem to work with hugs, so I used ghc with no problems. 1) save code to choices.hs, 2) ghc choices.hs, 3) ./a.out

    Ben Rogers

    September 3, 2007 at 8:47 am

  14. Thanks for the haskell version Ben. Now if someone will contribute an Erlang version, we’ll have a pretty full set 🙂

    Brian Adkins

    September 3, 2007 at 11:24 am

  15. Got a helpful response on comp.lang.lisp that replaced my print-choice function with a simple format. I’m really liking Common Lisp:

    (defun choices (menu &optional (sofar '()))
      (if menu
        (dolist (i (car menu))
          (choices (cdr menu) (append sofar (list i))))
        (format t "~{~a~^ ~}~%" sofar)))
    
    (choices (list
               (list "small" "medium" "large")
               (list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
               (list "cone" "cup")))
    

    Brian Adkins

    September 4, 2007 at 11:45 pm

  16. Prolog:

    choices([[small, medium, large],
    [vanilla, ‘ultra chocolate’, lychee, ‘rum raisin’, ginger],
    [cone, cup]]).

    Example query:

    ?- choices(Cs), maplist(member, C, Cs), maplist(format(“~w “), C), nl, fail.
    small vanilla cone
    small vanilla cup
    small ultra chocolate cone
    etc.

    mt

    September 5, 2007 at 6:26 am

  17. A Smalltalk version.

    “First, a new subclass called Counter was constructed from the Array class. Two variables were added to the class: slave and value. The following methods were added.”

    initialize
    	slave := nil. value := 1. ^self
    
    increment
    	value := value + 1.
    	value > self size
    		ifTrue:
    			[value := 1.
    			slave notNil ifTrue: [slave increment]]
    
    last
    	^value = self size and: [slave isNil ifFalse: [slave last] ifTrue: [true]]
    
    slave
    	^slave
    
    slave: anObject
    	slave := anObject
    
    value
    	Transcript show: (self at: value); show: ' '.
    	slave notNil ifTrue: [slave value].
    	^value.
    
    "The choices program."
    
    counter := Counter withAll: #('small' 'medium' 'large').
    counter slave: (Counter withAll: #('vanilla' ultra 'chocolate' 'lychee' 'rum raisin' 'ginger')).
    counter slave slave: (last := (Counter withAll: #('cone' 'cup'))).
    [counter last] whileFalse:
    	[x value.
    	x increment.
    	Transcript cr].
    x value
    

    PL

    September 6, 2007 at 9:07 pm

  18. Sorry – a typo in the Smalltalk program: left out a ‘ before ultra (for ‘ultra chocolate’).

    Also, the “last :=” is an artifact from a previous version, and while it causes no harm whatsoever, it can be removed.

    This is the cleaned up version. I ask that the moderator substitute this for the version above – THANKS!

    “The choices program.”

    counter := Counter withAll: #(‘small’ ‘medium’ ‘large’).
    counter slave: (Counter withAll: #(‘vanilla’ ‘ultra chocolate’ ‘lychee’ ‘rum raisin’ ‘ginger’)).
    counter slave slave: (Counter withAll: #(‘cone’ ‘cup’)).
    [counter last] whileFalse: [x value. x increment. Transcript cr].
    x value

    PL

    September 8, 2007 at 4:22 am

  19. Clean:

    items =: [[“small”,”medium”,”large”],[“vanilla”,”chocolate”],[“cup”,”cone”]]
    menu i
    | i == [] = “”
    = hd i +++ “n” +++ menu (tl i)
    Start = menu [x+++” “+++y+++” “+++z \ x

    PL

    September 30, 2007 at 10:18 am

  20. […] August, I wrote a blog post comparing a short function (from Brian Harvey’s home page) in Logo and several other […]

  21. I thought I’d put a first draft up of a version in Arc 🙂

    (def joinstr (lst (o sep " "))
      (if lst
        (string (car lst) (apply string (map [string sep _] (cdr lst))))
        ""))
    
    (def choices (menu (o result '()))
      (if menu
        (each x (car menu)
          (choices (cdr menu) (cons x result)))
        (prn (joinstr:rev result))))
    
    (choices (list
      (list "small" "medium" "large")
      (list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
      (list "cone" "cup")))
    

    Brian Adkins

    January 31, 2008 at 11:28 am

  22. After helpful feedback on the Arc forum and discovering join:

    (def choices (menu (o result '()))
      (if menu
        (each x (car menu)
          (choices (cdr menu) (join result (list x))))
        (prall result "n" " ")))
    
    (choices '(
      ("small" "medium" "large")
      ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
      ("cone" "cup")))
    

    Brian Adkins

    January 31, 2008 at 5:41 pm

  23. Sorry – couldn’t help writing another Haskell version:


    choices :: [[String]] -> IO ()
    choices xss = mapM_ (putStrLn . unwords) (f xss)
    where f [] = return []
    f (zs:zss) = do x

    Neil

    February 2, 2008 at 12:01 pm

  24. I hardly ever use HTML, so unsurprisingly I screwed up my first attempt to post a comment. Sorry (again)!

    choices :: [[String]] -> IO ()
    choices xss = mapM_ (putStrLn . unwords) (f xss)
        where f [] = return []
              f (zs:zss) = do x
    

    Neil

    February 2, 2008 at 12:04 pm

  25. Having just usefully taught myself how to use ampersands etc. in order to prevent “<-” being parsed as a comment, I can finally unveil my Haskell version.

    Thanks for your patience. (And fingers crossed for third attempt…)

    Ben’s Haskell version is shorter, of course, but I think mine might be more ‘idiomatic’ in that it abides by old Haskell maxim: ‘use monads whenever you see the slightest opportunity to show off the fact that you know how they work’.

    choices :: [[String]] -> IO ()
    choices xss = mapM_ (putStrLn . unwords) (f xss)
        where f [] = return []
              f (zs:zss) = do x <- zs
                              xs <- f zss
                              return $ x:xs
    
    main = choices [["small", "medium", "large"], ["vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger"], ["cone", "cup"]]
    

    Neil

    February 2, 2008 at 12:29 pm

  26. One more:

    
    choices xss = mapM_ (putStrLn . unwords) (sequence xss)
    
    main = choices [["small", "medium", "large"],
     ["vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger"],
     ["cone", "cup"]]
    
    

    Neil

    February 2, 2008 at 1:22 pm

  27. There are some APL, J & K versions of this program in this comp.lang.apl thread. Here is a version in J:

       Options=: ;: each ('small large medium');('ginger lychee rum_raisin ultra_choc vanilla');('cone cup')
       choices=: monad : ';:^:_1 >,{ y'
       choices Options
    small vanilla cone
    small vanilla cup
    small ultra_choc cone
    ...
    large rum_raisin cup
    large ginger cone
    large ginger cup
    

    Ric

    November 10, 2008 at 8:13 pm

  28. APL:
    
    ?,??.{?,' ',?}/('small' 'medium' 'large')('vanilla' 'ultra chocolate' 'lychee' 'rum raisin' 'ginger')('cone' 'cup')
    
    J (2 solutions):
    
    >,{ ('small';'medium';'large');('vanilla';'ultra chocolate';'lychee';'rum raisin';'ginger'); , { options
    

    XXX

    November 10, 2008 at 9:04 pm

  29. Brian, Enumerable::inject is the Ruby equivalent of Python’s reduce. Looks like Enumerable::reduce was introduced as a synonym in Ruby 1.8.7.

    Scott Moonen

    August 7, 2009 at 11:29 am

  30. A lot of the replies used Brian’s original technique of passing in a “sofar”. My Python version avoided this and did the concatenation on the return path, which seems a little more like the “functional way”. Brian pointed out to me that my original Python version misunderstood the intentions for “ultra chocolate”. A briefer and more correct version is available here: http://scott.andstuff.org/PythonSpikes

    Scott Moonen

    August 7, 2009 at 1:47 pm

  31. I’ve also tried a similar approach in Clojure. I tried to combine Clojure’s (for) macro with (gensym), but (for) didn’t like anything other than a literal vector, so I couldn’t make any progress there. Instead I took a simple recursive approach, as with many of the solutions above:

    (def choices
      '(("small" "medium" "large")
        ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
        ("cone" "cup")))
    
    (defn combo [l]
      (if (empty? (rest l))
        (first l)
        (for [x (first l) y (combo (rest l))] (str x " " y))))
    
    (doseq [x (combo choices)] (println x))
    

    Scott Moonen

    August 7, 2009 at 1:49 pm

  32. Ha, well, turns out that the clojure-contrib library, a standard part of any serious Clojure setup, has some built-in combinatorics support. That brings the Clojure sample down to a simple call to “cartesian-product”. I use “apply” below since cartesian-product expects the choices to be supplied as a series of arguments rather than a list of lists.

    (use 'clojure.contrib.combinatorics)
    
    (def choices
      '(("small" "medium" "large")
        ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
        ("cone" "cup")))
    
    (doseq [x (apply cartesian-product choices)] (apply println x))
    

    Scott Moonen

    August 17, 2009 at 12:04 pm

  33. […] a comment » In September 2007, Brian Adkins posted a simple Logo program to print all possible combinations of lists of items, and asked for alternatives in other […]

  34. I recently had a problem pop up where I needed to create a cartesian product of N lists. I’m coding it in Standard ML, so I now have a new entry in that language 🙂 Pretty concise I think:

    fun cartesian ([x]) = map (fn e => [e]) x
      | cartesian (x::xs) =
        let val tailCross = cartesian xs
        in concat(map (fn e => map (fn e2 => e::e2) tailCross) x) end
    
    fun choices xs = map join (cartesian xs)
    

    The Standard ML REPL abbreviated the list, but it works fine:

    - choices [["Small","Medium", "Large"],["vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger"],["cone", "cup"]];
    val it =
      ["Small vanilla cone","Small vanilla cup","Small ultra chocolate cone",
       "Small ultra chocolate cup","Small lychee cone","Small lychee cup",
       "Small rum raisin cone","Small rum raisin cup","Small ginger cone",
       "Small ginger cup","Medium vanilla cone","Medium vanilla cup",...]
      : string list
    

    Brian Adkins

    October 13, 2011 at 5:14 pm

  35. Here’s a better cartesian using nested folds that’s about twice as fast as the concat / map version:

    fun cartesian [] = []
      | cartesian ([x]) = map (fn e => [e]) x
      | cartesian (x::xs) =
        let val tailCross = cartesian xs
        in foldr (fn (x',result) =>
            foldr (fn (tc,l) => (x'::tc) :: l ) result tailCross) [] x
        end
    

    Brian Adkins

    October 16, 2011 at 4:28 pm

  36. Two more Haskell versions:

    cartesian []     = []
    cartesian [x]    = [[e] | e <- x]
    cartesian (x:xs) = [ x' : rest | x' <- x, rest <- cartesian xs ]
    
    cartesian [] = []
    cartesian [x] = map (e -> [e]) x
    cartesian (x:xs) = foldr (x' result ->
                     (foldr (tc l -> (x':tc):l) result tailCross)) [] x
       where tailCross = cartesian xs
    

    Brian Adkins

    August 4, 2012 at 1:37 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: