All Possible Matching Lists

Question

Implement a function that takes a list that consists of 0, 1 or 2, the list is called "pattern". Your job is to return all possible lists that match the pattern.

• 0 matches 0
• 1 matches 1
• 2 matches 0 and 1

Examples:

f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

Order does not matter, you can use a {set} data structure instead.

You cannot use regular expressions or other string pattern matching mechanisms. You cannot use a brute-force search.

Shortest solution wins.

Answer 1

Haskell, 49 characters

f[]=[[]]
f(2:r)=f(0:r)++f(1:r)
f(x:r)=map(x:)$f r

Interestingly this is exactly what I'd write even if this wasn't golf - except for removing spaces and calling the list's tail r rather than xs.

Answer 2

Haskell, 34 26 characters

Saved 8 characters thanks to Zgarb.

r 2=[0,1]
r n=[n]
f=mapM r

Answer 3

Prolog, 62 characters

f([],[]). f([H|T],[A|B]):-((H=2,(A=0;A=1));(H<2,A=H)),f(T,B).

Example:

?- f([0,2,0,2],X).
X = [0, 0, 0, 0] ;
X = [0, 0, 0, 1] ;
X = [0, 1, 0, 0] ;
X = [0, 1, 0, 1] ;

Answer 4

Mathematica, 30 chars

f=Tuples[{#}&/@#/.{2}->{0,1}]&

Examples:

f[{0, 1, 1}]

{{0, 1, 1}}

f[{0, 2, 0, 2}]

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}}

f[{2, 1, 0}]

{{0, 1, 0}, {1, 1, 0}}

Answer 5

Ruby - 76 characters

def f l;l==l-[2]?[l]:((j=l.dup)[k=l.index(2)]=0;(i=l.dup)[k]=1;f(j)+f(i))end

Testing script:

require_relative 'golf-lists'

[
  [0, 1, 1],
  [0, 2, 0, 2],
  [2, 1, 0]
].each do |list|
  puts "f([#{list.join(', ')}]) == #{f(list)}"
end

Result:

f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

Answer 6

Scheme (149) (148)

(define(f l)(if(null? l)'(())(let((t(f(cdr l)))(n(car l)))(if(< n 2)(map(lambda(m)`(,n,@m))t)`(,@(map(lambda(m)`(0,@m))t),@(map(lambda(m)`(1,@m))t]

With whitespace (the closing square brace closes all open parentheses on certain Scheme implementations; 154 chars without it):

(define (f l)
  (if (null? l)
      '(())
      (let ((t (f (cdr l)))(n(car l)))
        (if (< n 2)
            (map (lambda (m) `(,n ,@m)) t)
            `(,@(map (lambda (m) `(0 ,@m)) t)
              ,@(map (lambda (m) `(1 ,@m)) t]

Answer 7

CJam, 18 bytes

CJam is much younger than this challenge, so this is answer is not eligible for being accepted.

]]l~{2b\f{\f+~}}/p

Reads input from STDIN as a CJam style array.

Test it here.

Explanation

]]l~{2b\f{\f+~}}/p
]]                 "Push a nested empty array [[]] onto the stack. This is the base case.";
  l~               "Read and eval the input.";
    {          }/  "For each integer in the input.";
     2b            "Convert to base 2. This turns 0 into [0], 1 into [1] and 2 into [1 0].";
       \f{    }    "Swap with the current result and map this block onto the base-2 representation
                    copying in the current list of lists on each iteration.";
          \f+      "Swap the list of lists with the 0 or 1 and add the number to each list.";
             ~     "Unwrap the list of lists. They'll be regrouped by the surrounding f{...}.";
                 p "Pretty-print the result.";

Answer 8

Python 2, 156 bytes

def f(l):R,L=range(len(l)),[];exec"\n".join(" "*j+"for v%d in[[l[%d]],[0,1]][l[%d]>1]:"%(j,j,j)for j in R)+"L+=["+"".join("v%d,"%j for j in R)+"],";return L

Try it online!

Answer 9

J, 19 bytes

[:>@,[:{{&(0;1;0 1)

Try it online!

I had originally created a much longer version using amend and binary numbers, but user b_jonas suggested the above approach in IRC to me.

It essentially converts 0 and 1 to themselves, and 2 to the list 0 1, and the just cross products everything using catalog {. Since catalog requires boxed data, and returns structured data, everything is (un)raveled and unboxed at the end: >@,.