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

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 3

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]