# 產生可能的清單

## 解法

 000 [] 001 [3] 010 [2] 011 [2, 3] 100 [1] 101 [1, 3] 110 [1, 2] 111 [1, 2, 3]

000 => 100 => 010 => 110 => 001 => 101 => 011 => 111

• C
``#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 int indexOf(int, int*, int);void cleanTo(int, int*);int hasNext(int*, int);void next(int*, int);void printList(int*, int);int main(void) {    int digits[MAXSIZE] = {0};         int length;     printf("輸入清單個數：");     scanf("%d", &length);     printList(digits, length);    while(hasNext(digits, length)) {        next(digits, length);        printList(digits, length);    }    return 0; } int indexOf(int n, int* digits, int length) {    int i;    for(i = 0; i < length && digits[i] != n; i++);    return i == length ? -1 : i;}void cleanTo(int i, int* digits) {    int j;    for(j = 0; j < i; digits[j] = 0, j++);}int hasNext(int* digits, int length) {    return indexOf(0, digits, length) != -1;}void next(int* digits, int length) {    int i = indexOf(0, digits, length);    cleanTo(i, digits);    digits[i] = 1;}void printList(int* digits, int length) {    int i = indexOf(1, digits, length);    printf(i == -1 ? "[" : "[%d", i + 1);    int j;    for(j = i + 1; j < length; j++) if(digits[j] == 1) {        printf(", %d", j + 1);     }    printf("]\n");}``

• Java
``import java.util.*;public class PossibleList {    private static class Binary<T> {        int[] digits;                Binary(int[] digits) { this.digits = digits; }                int indexOf(int elem) {            int i;            for(i = 0; i < digits.length && digits[i] != elem; i++);            return i == digits.length ? -1 : i;        }                boolean hasNext() { return indexOf(0) != -1; }                Binary<T> next() {            int i = indexOf(0);            int[] nextDigits = Arrays.copyOf(digits, digits.length);            for(int j = 0; j < i; nextDigits[j] = 0, j++);            nextDigits[i] = 1;            return new Binary<>(nextDigits);        }                public List<T> toList(List<T> src) {            List<T> lt = new ArrayList<>();            int i = indexOf(1);            if(i != -1) {                for(int j = i; j < digits.length; j++) if(digits[j] == 1) {                    lt.add(src.get(j));                }            }            return lt;        }    }        public static <T> List<List<T>> from(List<T> src) {        Binary<T> binary = new Binary<>(new int[src.size()]);        List<List<T>> all = new ArrayList<>();        all.add(binary.toList(src));        while(binary.hasNext()) {            binary = binary.next();            all.add(binary.toList(src));        }        return all;    }        public static void main(String[] args) {        for(List<Integer> lt : from(Arrays.asList(1, 2, 3, 4))) {            System.out.println(lt);        }    }}``

• Python
``from functools import reduceclass Binary:    def __init__(self, digits):        self.digits = digits    def hasNext(self):        return 0 in self.digits    def next(self):        i = self.digits.index(0) if 0 in self.digits else -1        return Binary([0] * i + [1] + self.digits[i + 1:])    def toList(self, src):        return reduce(lambda acc, t: acc + [t[1]] if t[0] == 1 else acc,                      zip(self.digits, src), [])def possibleLts(src):    def iter(binary):        return [binary.toList(src)] + \            (iter(binary.next()) if binary.hasNext() else [])    return iter(Binary([0] * len(src)))    for lt in possibleLts([1, 2, 3, 4]):    print(lt)``

• Scala
``def list[T](elem: T, length: Int) = for(i <- 0 until length) yield elemclass Binary[T](digits: List[Int]) {    def hasNext = digits.contains(0)    def next = {        val i = if(digits.contains(0)) digits.indexOf(0) else -1        new Binary[T](            (list(0, i) :\ (1 :: digits.drop(i + 1)))(_ :: _))    }    def toList(src: List[T]) = {        (digits.zip(src) :\ (Nil : List[T]))(            (t, acc) => if(t._1 == 1) t._2 :: acc else acc)    }}def from[T](src: List[T]) = {    def iterate(binary: Binary[T]): List[List[T]] = {        binary.toList(src) :: (            if(binary.hasNext) iterate(binary.next) else Nil)    }    iterate(new Binary[T]((list(0, src.size)).toList))}from(List(1, 2, 3, 4)).foreach(println)``

• Ruby
``class Binary    def initialize(digits)        @digits = digits    end    def hasNext        @digits.include? 0    end    def next        i = @digits.index(0)        Binary.new([0] * i + [1] + @digits.drop(i + 1))    end    def toList(src)        @digits.zip(src).reduce([]) { |acc, t|             t[0] == 1 ? acc + [t[1]] : acc         }    endenddef possibleLts(src)    iter = ->(binary) {        [binary.toList(src)] +             (binary.hasNext ? iter.call(binary.next) : [])    }    iter.call(Binary.new([0] * src.size))end    possibleLts([1, 2, 3, 4]).each do |lt|    print("#{lt}\n")end``

• JavaScript
``function list(elem, length) {    var lt = [];    for(var i = 0; i < length; i++) { lt.push(elem); }    return lt;}function Binary(digits) { this.digits = digits; }Binary.prototype.hasNext = function() {    return this.digits.indexOf(0) != -1;};Binary.prototype.next = function() {    var i = this.digits.indexOf(0);    return new Binary(list(0, i).concat(        [1].concat(this.digits.slice(i + 1, this.digits.length))));};Binary.prototype.toList = function(src) {    var lt = [];    var i = this.digits.indexOf(1);    if(i != -1) {        for(var j = i; j < this.digits.length; j++) if(this.digits[j] == 1) {            lt.push(src[j]);        }    }    return lt;};function from(src) {    var binary = new Binary(list(0, src.length));    var all = [];    all.push(binary.toList(src));    while(binary.hasNext()) {        binary = binary.next();        all.push(binary.toList(src));    }    return all;}from([1, 2, 3, 4]).forEach(function(lt) {    print(lt);});``

``import Data.List (elemIndex)hasNext digits = 0 `elem` digitsnext digits =    (replicate i 0) ++ (1 : (drop (i + 1) digits))    where (Just i) = 0 `elemIndex` digits    toList digits src =    foldr (\t acc -> if fst t == 1 then snd t : acc                      else acc) [] \$ zip digits srcpossibleLts src = iter \$ replicate (length src) 0    where        iter digits =             toList digits src : if hasNext digits                                     then iter \$ next digits                                     else []            main = sequence [print lt | lt <- possibleLts [1, 2, 3, 4]]``