# m 元素清單的 n 元素子清單

## 解法

[1 2 3]
[1 2 4]
[1 2 5]
[1 3 4]
[1 3 5]
[1 4 5]
[2 3 4]
[2 3 5]
[2 4 5]
[3 4 5]

1. 如果最右元素小於m，該元素遞增1
2. 如果清單list最右元素等於m，則遞增1的位置pos為第一個list[pos + 1] - list[pos] > 1的位置
3. 每次遞增1的位置往左移後，必須重新調整右邊的元素為遞減順序

• C
``#include <stdio.h> #include <stdlib.h> #define MAX 20 void init(int*, int);int position(int*, int, int);void next(int*, int, int);void print(int*, int);int main(void) {     int list[MAX] = {0};    int m, n;         printf("清單個數 m：");     scanf("%d", &m);     printf("取出個數 n：");     scanf("%d", &n);         init(list, n);    print(list, n);    while(hasNext(list, m, n)) {        next(list, m, n);        print(list, n);    }     return 0; }void init(int* list, int n) {    int i;    for(i = 0; i < n; i++) { list[i] = i + 1; }}int position(int* list, int m, int n) {    if(list[n - 1] != m) {        return n - 1;    }    else {        int pos = n - 2;        while(list[pos + 1] - list[pos] == 1) { pos--; }        return pos;    }}int hasNext(int* list, int m, int n) {    return list[0] < m - n + 1;}void next(int* list, int m, int n) {    int pos = position(list, m, n);    list[pos]++;     int i;    for(i = pos + 1; i < n; i++) { list[i] = list[i - 1] + 1; }}void print(int* list, int n) {    int i;            for(i = 0; i < n; i++) { printf("%d ", list[i]); }    putchar('\n'); }``

• Java
``import java.util.*;public class SubList {    public static class IdxArray<T> {        private int m;        private int[] idxArray;                private IdxArray(int m, int[] idxArray) {            this.m = m;            this.idxArray = idxArray;        }                public boolean hasNext() {            return idxArray[0] < m - idxArray.length;        }                public IdxArray<T> next() {                        int[] idxArr = Arrays.copyOf(idxArray, idxArray.length);            int pos = position();            idxArr[pos]++;            for(int i = pos + 1; i < idxArr.length; i++) {                idxArr[i] = idxArr[i - 1] + 1;            }            return new IdxArray<>(m, idxArr);        }                public List<T> toList(List<T> src) {            List<T> lt = new ArrayList<>();            for(int idx : idxArray) { lt.add(src.get(idx)); }            return lt;        }                private int position() {            if(idxArray[idxArray.length - 1] != m - 1) {                return idxArray.length - 1;            }            else {                int pos = idxArray.length - 2;                while(idxArray[pos + 1] - idxArray[pos] == 1) { pos--; }                return pos;            }        }                public static <T> IdxArray<T> get(int m, int n) {            int[] idxArray = new int[n];            for(int i = 0; i < n; i++) {                idxArray[i] = i;            }            return new IdxArray<>(m, idxArray);        }    }        public static <T> List<List<T>> from(List<T> src, int n) {        IdxArray<T> idxArray = IdxArray.get(src.size(), n);        List<List<T>> all = new ArrayList<>();        all.add(idxArray.toList(src));        while(idxArray.hasNext()) {            idxArray = idxArray.next();            all.add(idxArray.toList(src));        }        return all;    }    public static void main(String[] args) {        List<Integer> src = Arrays.asList(1, 2, 3, 4, 5);        for(List<Integer> lt : from(src, 3)) {            System.out.println(lt);        }    }}``

• Python
``class IdxArray:    def __init__(self, m, idxArray):        self.m = m        self.idxArray = idxArray            def position(self):        idxArray = self.idxArray        def oneDif(pos):            return (oneDif(pos - 1)                 if idxArray[pos + 1] - idxArray[pos] == 1 else pos)        return (len(idxArray) - 1                    if idxArray[len(idxArray) - 1] != self.m - 1                    else oneDif(len(idxArray) - 2))            def hasNext(self):        return self.idxArray[0] < self.m - len(self.idxArray)            def next(self):        pos = self.position()        idxArray = self.idxArray        return IdxArray(self.m, idxArray[0:pos] +            list(range(idxArray[pos] + 1,                 idxArray[pos] + 1 + len(idxArray) - pos)))            def toList(self, src):        return [src[idx] for idx in self.idxArray]    @staticmethod        def subList(m, n):        return IdxArray(m, list(range(n)))    def subLts(src, n):    def iter(idxArray):        return ([idxArray.toList(src)] +             (iter(idxArray.next()) if idxArray.hasNext() else []))    return iter(IdxArray.subList(len(src), n))    for lt in subLts([1, 2, 3, 4, 5], 3):    print(lt)``

• Scala
``class IdxList[T] private (m: Int, idxList: List[Int]) {    def pos = {        def oneDif(p: Int): Int = {            if(idxList(p + 1) - idxList(p) == 1) oneDif(p - 1)             else p        }        if(idxList(idxList.size - 1) != m - 1) idxList.size - 1         else oneDif(idxList.size - 2)    }        def hasNext = idxList(0) < m - idxList.size        def next = {        new IdxList[T](m, idxList.slice(0, pos) ++           ((idxList(pos) + 1) to (idxList(pos) + idxList.size - pos)).toList)    }        def toList(src: List[T]) =         (for(idx <- idxList) yield src(idx)).toList}object IdxList {    def apply[T](m: Int, n: Int) = new IdxList[T](m, (0 until n).toList)}def from[T](src: List[T], n: Int) = {    def iter(idxList: IdxList[T]): List[List[T]] = {        idxList.toList(src) ::             (if(idxList.hasNext) iter(idxList.next) else Nil)    }    iter(IdxList(src.size, n))}from(List(1, 2, 3, 4, 5), 3).foreach(println)``

• Ruby
``class IdxList    def initialize(m, idxArray)        @m = m        @idxArray = idxArray    end            def pos        oneDif = ->(p) {            @idxArray[p + 1] - @idxArray[p] == 1 ? oneDif.call(p - 1) : p        }        @idxArray[@idxArray.size - 1] != @m - 1 ?             @idxArray.size - 1 : oneDif.call(@idxArray.size - 2)    end            def hasNext        @idxArray[0] < @m - @idxArray.size    end            def next        IdxList.new(@m,             @idxArray[0...pos] + ((@idxArray[pos] + 1) ..                (@idxArray[pos] + @idxArray.size - pos)).to_a        )    end            def toList(src)        @idxArray.map {|idx| src[idx]}    end    def self.subList(m, n)        IdxList.new(m, (0...n).to_a)    endenddef subLts(src, n)    iter = ->(idxArray) {        [idxArray.toList(src)] +             (idxArray.hasNext ? iter.call(idxArray.next) : [])    }    iter.call(IdxList.subList(src.size, n))endsubLts([1, 2, 3, 4, 5], 3).each do |lt|    print("#{lt}\n")end``

• JavaScript
``function IdxArray(m, idxArray) {    this.m = m;    this.idxArray = idxArray;}IdxArray.prototype.hasNext = function() {    return this.idxArray[0] < this.m - this.idxArray.length;};IdxArray.prototype.position = function() {    if(this.idxArray[this.idxArray.length - 1] != this.m - 1) {        return this.idxArray.length - 1;    }    else {        var pos = this.idxArray.length - 2;        while(this.idxArray[pos + 1] - this.idxArray[pos] == 1) { pos--;}        return pos;    }};IdxArray.prototype.next = function() {    var pos = this.position();    var idxArr = this.idxArray.slice(0, pos);    idxArr.push(this.idxArray[pos] + 1);    for(var i = pos + 1; i < this.idxArray.length; i++) {        idxArr.push(idxArr[i - 1] + 1);    }    return new IdxArray(this.m, idxArr);};IdxArray.prototype.toList = function(src) {    return this.idxArray.map(function(idx) { return src[idx]; });};IdxArray.get = function(m, n) {    var idxArray = [];    for(var i = 0; i < n; i++) { idxArray.push(i); }    return new IdxArray(m, idxArray);};function from(src, n) {    var idxArray = IdxArray.get(src.length, n);    var all = [];    all.push(idxArray.toList(src));    while(idxArray.hasNext()) {        idxArray = idxArray.next();        all.push(idxArray.toList(src));    }    return all;}from([1, 2, 3, 4, 5], 3).forEach(function(lt) { print(lt); });``

``data IdxList = IdxList Int [Int] deriving (Show)hasNext (IdxList m idxLt)= idxLt !! 0 < m - length idxLtpos (IdxList m idxLt) =    if idxLt !! (length idxLt - 1) /= m - 1 then length idxLt - 1    else oneDif (length idxLt - 2)    where         oneDif p =            if idxLt !! (p + 1) - idxLt !! p == 1 then oneDif \\$ p - 1            else pnext idxList@(IdxList m idxLt) =     IdxList m (take p idxLt ++         [(idxLt !! p + 1) .. (idxLt !! p + length idxLt - p)])    where p = pos idxListtoList (IdxList _ idxLt) src = [src !! idx | idx <- idxLt]get m n = IdxList m [0 .. n - 1]from src n = iter \\$ get (length src) n    where        iter idxList =             toList idxList src : if hasNext idxList                                     then iter \\$ next idxList                                    else []                                    main = sequence [print lt | lt <- from [1, 2, 3, 4, 5] 3]``