子集

December 8, 2021

給定一組數字或符號，從中挑選元素產生所有可能的子集（包括空集），例如給定 1 2 3，可能的集合會是 []、[3]、[2]、[2, 3]、[1]、 [1, 3]、[1, 2]、[1, 2, 3]，進一步地，可以考量字典順序，例如 []、[1]、[1, 2]、[1, 2, 3]、[1, 3]、[2]、[2, 3]、[3]。

解法思路

如果不考量順序，可以思考二進位數字加法，並留意 1 出現的位置，若每個位置對應一個數字，由 1 對應的數字產生的就是一個子集。例如：
000 -> []
001 -> [3]
010 -> [2]
011 -> [2, 3]
100 -> [1]
101 -> [1, 3]
110 -> [1, 2]
111 -> [1, 2, 3]

如何產生二進位數？有許多方法可以使用，C 語言的話，可以使用 unsigned 型別加上 & 位元運算來產生，具有陣列的言，首先陣列內容全為 0；接著找第一個 0，在還沒找到前將走訪過的元素變為 0，而第一個找到的 0 變為 1，重複這個動作，直到陣列元素都變為 1 為止。例如：

000 => 100 => 010 => 110 => 001 => 101 => 011 => 111

如果要有字典順序，例如 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]，觀察後可發現：
[] => [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 個元素，要從中產生可能的子集，依序產生子集時：

  1. 從空集開始，依序加入後續元素，直到子集最後一個數為 n。
  2. 若此時倒數第二個元素是 m，下個子集就是去掉 n，而最後一個元素是 m + 1，例如 [1, 2, 3, 4, …, m, n]，下個子集就是 [1, 2, 3, 4, …, m + 1]，再依序加入後續元素。
  3. 加入 m + 1 的後續元素，直到子集最後一個數為 n。
  4. 重複 1 到 3。

例如 1 2 3 4，從中產生 [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]。

程式實作：無順序

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

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

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)

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)

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

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

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

程式實作：字典順序

#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]++;      // 下一個子集尾數 
    } 
}

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

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)

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)

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

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

分享到 LinkedIn 分享到 Facebook 分享到 Twitter