# 子集

December 8, 2021

## 解法思路

000 -> []
001 -> [3]
010 -> [2]
011 -> [2, 3]
100 -> [1]
101 -> [1, 3]
110 -> [1, 2]
111 -> [1, 2, 3]

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

[] => [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，例如 [1, 2, 3, 4, …, m, n]，下個子集就是 [1, 2, 3, 4, …, m + 1]，再依序加入後續元素。
3. 加入 m + 1 的後續元素，直到子集最後一個數為 n。
4. 重複 1 到 3。

## 程式實作：無順序

``````#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) {
}
}
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<>();
while(binary.hasNext()) {
binary = binary.next();
}
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) {
}
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<>();
while(idxList.hasNext()) {
idxList = idxList.next();
}
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]]
``````