# 產生可能的集合（字典順序）

## 解法

[] => [1] => [1, 2] => [1, 2, 3] => [1, 2, 3, 4] =>
[1, 2, 4] =>
[1, 3] => [1, 3, 4] =>
[1, 4] =>
[2] => [2, 3] => [2, 3, 4] =>
[2, 4] =>
[3] => [3, 4] =>
[4]

1. 從空清單開始，依序加入後續元素，直到清單最後一個數為n。
2. 若此時倒數第二個元素是m，則下個清單就是去掉n，而最後一個元素是 m + 1。
3. 然後加入m + 1的後續元素，直到清單最後一個數為n，重複1到3。

{1, 2, 3, 4, ..., m, n}

• C
``#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 void print(int*);int getPosition(int*);int hasNext(int*, int);void next(int*, int);int main(void) {     int list[MAXSIZE] = {0};     int n;    printf("輸入清單個數：");     scanf("%d", &n);         print(list);    while(hasNext(list, n)) {        next(list, n);        print(list);    }    return 0; }void print(int* list) {    printf("[");    int i, position;    for(i = 0, position = getPosition(list); i < position; i++) {        printf("%d, ", list[i]);     }    printf(position == -1 ? "]\n" : "%d]\n", list[i]);}int getPosition(int* list) {    int i;    for(i = 0; list[i] != 0; i++);    return i - 1;}int hasNext(int* list, int n) {    int position = getPosition(list);    return position == -1 || list[position] < n || position != 0;}void next(int* list, int n) {    int position = getPosition(list);    if(position == -1) {           // 第一個非空清單        list[0] = 1;    }    else if(list[position] < n) {  // 遞增清單個數         list[position + 1] = list[position] + 1;     }     else if(position != 0) {       // 如果不是第一個位置         list[position] = 0;        list[position - 1]++;      // 下一個清單尾數     } }``

• Java
``import java.util.*;public class PossibleList2 {    public static class IdxList<T> {        private List<Integer> idxLt;        private int n;                public IdxList(int n) {             this(n, new ArrayList<>());        }                private IdxList(int n, List<Integer> idxLt) {            this.n = n;            this.idxLt = idxLt;        }                public boolean hasNext() {            return idxLt.isEmpty() ||                    getLast(idxLt) < n - 1 || idxLt.size() != 1;        }                public IdxList<T> next() {            List<Integer> newIdxLt = new ArrayList<>();            if(idxLt.isEmpty()) { newIdxLt.add(0); }            else if(getLast(idxLt) < n - 1) {                newIdxLt.addAll(idxLt);                newIdxLt.add(getLast(idxLt) + 1);            }            else if(idxLt.size() != 1) {                newIdxLt.addAll(idxLt.subList(0, idxLt.size() - 2));                newIdxLt.add(idxLt.get(idxLt.size() - 2) + 1);            }            return new IdxList<>(n, newIdxLt);        }                public List<T> toList(List<T> src) {            List<T> lt = new ArrayList<>();            for(Integer idx : idxLt) { lt.add(src.get(idx)); }            return lt;        }                private static Integer getLast(List<Integer> idxList) {            return idxList.get(idxList.size() - 1);        }    }        public static <T> List<List<T>> from(List<T> src) {        IdxList<T> idxList = new IdxList<>(src.size());        List<List<T>> all = new ArrayList<>();        all.add(idxList.toList(src));        while(idxList.hasNext()) {            idxList = idxList.next();            all.add(idxList.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
``class IdxList:    def __init__(self, n, idxLt = []):        self.n = n        self.idxLt = idxLt    def hasNext(self):        return len(self.idxLt) == 0 or \               self.idxLt[-1] < self.n - 1 or \               len(self.idxLt) != 1    def next(self):        idxLt = self.idxLt        return IdxList(self.n,             [0] if len(idxLt) == 0 else             (idxLt + [idxLt[-1] + 1] if idxLt[-1] < self.n - 1 else (            idxLt[0 : len(idxLt) - 2] + [idxLt[-2] + 1] if len(idxLt) != 1                                                        else []))        )     def toList(self, src):        return [src[idx] for idx in self.idxLt]                def possibleLts(src):    def iter(idxList):        return [idxList.toList(src)] + \            (iter(idxList.next()) if idxList.hasNext() else [])    return iter(IdxList(len(src)))    for lt in possibleLts([1, 2, 3, 4]):    print(lt)``

• Scala
``class IdxList[T](n: Int, idxLt: List[Int]) {    def this(n: Int) = this(n, Nil);    def hasNext =        idxLt.size == 0 || idxLt.head < n - 1 || idxLt.size != 1        def next = new IdxList[T](n,         if(idxLt.size == 0) List(0)        else if(idxLt.head < n - 1) (idxLt.head + 1) :: idxLt        else if(idxLt.size != 1) (idxLt.tail.head + 1) :: idxLt.tail.tail        else Nil    )        def toList(src: List[T]) =         (for(idx <- idxLt.reverse) yield src(idx)).toList}def from[T](src: List[T]) = {    def iterate(idxList: IdxList[T]): List[List[T]] = {        idxList.toList(src) :: (            if(idxList.hasNext) iterate(idxList.next) else Nil)    }    iterate(new IdxList[T](src.size))}from(List(1, 2, 3, 4)).foreach(println)``

• Ruby
``class IdxList    def initialize(n, idxLt = [])        @n = n        @idxLt = idxLt    end            def hasNext        @idxLt.empty? || @idxLt.last < @n - 1 || @idxLt.size != 1    end        def next        IdxList.new(@n,             if @idxLt.empty?                [0]            elsif @idxLt.last < @n - 1                @idxLt + [@idxLt.last + 1]            elsif @idxLt.size != 1                @idxLt.take(@idxLt.size - 2) + [@idxLt[-2] + 1]            else                []            end        )    end                    def toList(src)        @idxLt.map {|idx| src[idx]}    endend                def possibleLts(src)    iter = ->(idxList) {        [idxList.toList(src)] +             (idxList.hasNext ? iter.call(idxList.next) : [])    }    iter.call(IdxList.new(src.size))end    possibleLts([1, 2, 3, 4]).each do |lt|    print("#{lt}\n")end``

• JavaScript
``Array.prototype.getLast = function() { return this[this.length - 1]; };Array.prototype.isEmpty = function() { return this.length == 0; };function IdxList(n, idxLt) {    this.n = n;    this.idxLt = idxLt;}IdxList.prototype.hasNext = function() {    var idxLt = this.idxLt;    return idxLt.isEmpty() || idxLt.getLast() < this.n - 1                            || idxLt.length != 1;};IdxList.prototype.next = function() {    var newIdxLt = [];    var idxLt = this.idxLt;    if(idxLt.isEmpty()) {        newIdxLt.push(0);    }    else if(idxLt.getLast() < this.n - 1) {        idxLt.forEach(function(idx) { newIdxLt.push(idx); });        newIdxLt.push(idxLt.getLast() + 1);    }    else if(idxLt.length != 1) {        idxLt.slice(0, idxLt.length - 2).forEach(function(idx)             { newIdxLt.push(idx); }        );        newIdxLt.push(idxLt[idxLt.length - 2] + 1);    }    return new IdxList(this.n, newIdxLt);};IdxList.prototype.toList = function(src) {    return this.idxLt.map(function(idx) { return src[idx]; });};function from(src) {    var idxList = new IdxList(src.length, []);    var all = [];    all.push(idxList.toList(src));    while(idxList.hasNext()) {        idxList = idxList.next();        all.push(idxList.toList(src));    }    return all;}from([1, 2, 3, 4]).forEach(function(lt) { print(lt); });``

``data IdxList = IdxList Int [Int] deriving (Show)hasNext (IdxList n idxLt) =    null idxLt || head idxLt < n - 1 || length idxLt /= 1next (IdxList n idxLt) =     IdxList n (        if null idxLt then [0]        else if head idxLt < n - 1              then head idxLt + 1 : idxLt        else if length idxLt /= 1              then (head \\$ tail idxLt) + 1 : (tail \\$ tail idxLt)        else [])    toList (IdxList _ idxLt) src = [src !! idx | idx <- idxLt]possibleLts src = iter \\$ IdxList (length src) []    where        iter idxList =             toList idxList src : if hasNext idxList                                     then iter \\$ next idxList                                    else []                                    main = sequence [print lt | lt <- possibleLts [1, 2, 3, 4]]``