From Gossip@caterpillar

Algorithm Gossip: 產生可能的集合

說明

給定一組數字或符號，產生所有可能的集合（包括空集合），例如給定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}

瞭解這個方法之後，剩下的就是如何產生二進位數？有許多方法可以使用，您可以使用unsigned型別加上&位元運算來產生，這邊則是使用陣列搜尋，首先陣列內容全為0，找第一個1，在還沒找到之前將走訪過的內容變為0，而第一個找到的0則變為 1，如此重複直到所有的陣列元素都變為1為止，例如：

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

如果要產生字典順序，例如若有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的話，例如：

{a b c d e n}

則下一個集合就是{a b c d e+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

實作：字典順序 C Java Python Scala Ruby

C（無字典順序）

#include <stdio.h> 
#include <stdlib.h> 

#define MAXSIZE 20 

int main(void) { 
    char digit[MAXSIZE]; 
    
    int n; 
    printf("輸入集合個數："); 
    scanf("%d", &n); 

    int i;
    for(i = 0; i < n; i++) 
        digit[i] = '0'; 

    printf("\n{}"); // 空集合 

    while(1) { 
        // 找第一個0，並將找到前所經過的元素變為0 
        int i;
        for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++); 
        if(i == n)  // 找不到0 
            break; 
        else          // 將第一個找到的0變為1 
            digit[i] = '1'; 

        int j;
        // 找第一個1，並記錄對應位置 
        for(j = 0; j < n && digit[j] == '0'; j++); 
        printf("\n{%d", j + 1); 
        int k;
        for(k = j + 1; k < n; k++) 
            if(digit[k] == '1') 
                printf(",%d", k + 1); 

        printf("}"); 
    } 
    
    printf("\n"); 

    return 0; 
}

Java（無字典順序）

public class PossibleSet {
    public static void main(String[] args) {
        char[] digit = new char[4]; 

        for(int i = 0; i < digit.length; i++) 
            digit[i] = '0'; 

        System.out.println("{}"); // 空集合 

        while(true) { 
            // 找第一個0，並將找到前所經過的元素變為0
            int i;
            for(i = 0; i < digit.length && digit[i] == '1'; 
                digit[i] = '0', i++); 

            if(i == digit.length)  // 找不到0 
                break; 
            else          // 將第一個找到的0變為1 
                digit[i] = '1'; 

            // 找第一個1，並記錄對應位置 
            int j;
            for(j = 0; j < digit.length && digit[j] == '0'; j++); 

            System.out.print("{" + (j+1)); 
        
            for(int k = j + 1; k < digit.length; k++) 
                if(digit[k] == '1') 
                    System.out.print(", " + (k + 1)); 

            System.out.println("}"); 
        } 
    }
}

Python（無字典順序）

digit = ['0'] * 4
print("{}")
while True:
    i = 0
    while i < len(digit) and digit[i] == '1':
        digit[i] = '0'
        i += 1
    if i == len(digit):
        break
    else:
        digit[i] = '1'
    j = 0
    while j < len(digit) and digit[j] == '0':
        j += 1
    print("{", j + 1, end="")
    for k in range(j + 1, len(digit)):
        if digit[k] == '1':
            print(", ", k + 1, end="")
    print("}")

Scala（無字典順序）

val digit = new Array[Char](4)
for(i <- 0 until digit.length) {
    digit(i) = '0'
}

println("{}")

var isContinue = true
do {
    var i = 0
    while(i < digit.length && digit(i) == '1') {
        digit(i) = '0'
        i += 1
    }
    if(i != digit.length) {
        digit(i) = '1'
        var j = 0
        while(j < digit.length && digit(j) == '0') {
            j += 1
        }
        print("{" + (j + 1))
        for(
            k <- j + 1 until digit.length
            if digit(k) == '1'
        ) print(", " + (k + 1))
        println("}")
    }
    else {
        isContinue = false
    }
} while(isContinue)

Ruby（無字典順序）

digit = Array.new(4, "0")
puts "{}"
while true
    i = 0
    while i < digit.length && digit[i] == '1'
        digit[i] = "0"
        i += 1
    end
    if i == digit.length
        break
    else
        digit[i] = "1"
    end
    j = 0
    while j < digit.length && digit[j] == "0"
        j += 1
    end
    print "{", j + 1
    (j + 1).upto(digit.length - 1) { |k|
        if digit[k] == "1"
            print ", ", k + 1
        end
    }
    puts "}"
end

C（字典順序）

#include <stdio.h> 
#include <stdlib.h> 

#define MAXSIZE 20 

int main(void) { 
    int set[MAXSIZE]; 
    int i, n, position = 0; 

    printf("輸入集合個數："); 
    scanf("%d", &n); 
    printf("\n{}"); 
    set[position] = 1; 

    while(1) { 
        printf("\n{%d", set[0]);  // 印第一個數 
        for(i = 1; i <= position; i++) 
            printf(",%d", set[i]); 
        printf("}"); 

        if(set[position] < n) {  // 遞增集合個數 
            set[position+1] = set[position] + 1; 
            position++; 
        } 
        else if(position != 0) {  // 如果不是第一個位置 
            position--;       // 倒退 
            set[position]++;  // 下一個集合尾數 
        } 
        else  // 已倒退至第一個位置 
            break; 
    } 

    printf("\n"); 

    return 0; 
}

Java（字典順序）

public class PossibleSet {
    public static void main(String[] args) {
        int[] set = new int[4]; 
        int position = 0; 
        set[position] = 1; 

        while(true) { 
            System.out.print("{" + set[0]);  // 印第一個數 
            for(int i = 1; i <= position; i++) 
                System.out.print("," + set[i]); 
            System.out.print("}"); 

            if(set[position] < set.length) {  // 遞增集合個數 
                set[position+1] = set[position] + 1; 
                position++; 
            } 
            else if(position != 0) {  // 如果不是第一個位置 
                position--;       // 倒退 
                set[position]++;  // 下一個集合尾數 
            } 
            else  // 已倒退至第一個位置 
                break; 
        } 
    }
}

Python（字典順序）

set = [1, 0, 0, 0]
position = 0
while True:
    print("{", set[0], end="")
    for i in range(1, position + 1):
        print(" ,", set[i], end="")
    print("}")
    if set[position] < len(set):
        set[position + 1] = set[position] + 1
        position += 1
    elif position != 0:
        position -= 1
        set[position] += 1
    else:
        break

Scala（字典順序）

val set = new Array[Int](4)
var position = 0
set(position) = 1
var isContinue = true
do {
    print("{" + set(0))
    for(i <- 1 to position)
        print("," + set(i))
    print("}")
    if(set(position) < set.length) {
        set(position + 1) = set(position) + 1
        position += 1
    }
    else if(position != 0) {
        position -= 1
        set(position) += 1
    }
    else {
        isContinue = false
    }
} while(isContinue)

Ruby（字典順序）

set = [1, 0, 0, 0]
position = 0
while true
    print "{", set[0]
    1.upto(position) { |i|
        print ", ", set[i]
    }
    puts "}"
    if set[position] < set.length
        set[position + 1] = set[position] + 1
        position += 1
    elsif position != 0
        position -= 1
        set[position] += 1
    else
        break
    end
end