產生可能的清單

說明

解法

實作：C    Java    Python    Scala    Ruby    JavaScript    Haskell

• 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 reduce

class 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 elem

class 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 
        }
    end
end

def 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);
});

• Haskell

import Data.List (elemIndex)

hasNext digits = 0 `elem` digits

next 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 src

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