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

說明

假設有個清單擁有m個元素，任意從清單中取出n個元素，則這n個元素形成的可能子清單有哪些？

解法

假設有5個元素的清單，任意取出3個元素的可能子清單如下：

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

這些子清單示範使用字典順序排列，如此可觀察出一些規則：

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

關鍵在於哪個位置必須進行加1動作，到底是最右位置要加1？還是其它位置？

實作：C Java Python Scala Ruby JavaScript Haskell

#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)
    end
end

def subLts(src, n)
    iter = ->(idxArray) {
        [idxArray.toList(src)] + 
            (idxArray.hasNext ? iter.call(idxArray.next) : [])
    }
    iter.call(IdxList.subList(src.size, n))
end

subLts([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); });

Haskell

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

hasNext (IdxList m idxLt)= idxLt !! 0 < m - length idxLt

pos (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 p

next idxList@(IdxList m idxLt) = 
    IdxList m (take p idxLt ++ 
        [(idxLt !! p + 1) .. (idxLt !! p + length idxLt - p)])
    where p = pos idxList

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