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

說明

接續產生可能的清單。現在要考慮產生的清單必須具備字典順序。例如給定1 2 3 4，必須產生[]、[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]。

解法

如果要產生字典順序，例如有4個元素，則觀察後可發現：

[] => [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]

簡單地說，如果有n個元素的清單要從中產生可能的清單，當依序產生清單時：

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

例如：

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

則下一個清單就是[1, 2, 3, 4, ..., m + 1]，再依序加入後續的元素。

例如有四個元素的清單，從中產生[1, 2, 3, 4]集合時，則下一個清單就是[1, 2, 3 + 1]，也就是[1, 2, 4]，由於最後一個元素還是4，所以下一個清單就是[1, 2 + 1]，也就是[1, 3]，接下來再加入後續元素4，也就是[1, 3, 4]，由於又遇到元素4，所以下一個清單是[1, 3 + 1]，也就是[1, 4]。

實作：C Java Python Scala Ruby JavaScript Haskell

#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]}
    end
end
                
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); });

Haskell

data IdxList = IdxList Int [Int] deriving (Show)

hasNext (IdxList n idxLt) =
    null idxLt || head idxLt < n - 1 || length idxLt /= 1

next (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]]