All Possible Matching Lists

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.

-

``````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`.

-

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]]
``````
-

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]
``````
-