Re: [問題] 使用遞迴或使用其他迴圈方式

[dryman (dryman)]

這就是標準的power set的問題

假設你的布是四公分，將可以切的點設為a,b,c
組合有：
{}      都沒切，完整四公分
{a}     切一刀，一公分-三公分
{a,b}   切兩刀，一公分-一公分-二公分
{a,b,c}
{b}
{b,c}
{c}     依此類推

雖然power set可以用遞迴解出所有解，但那樣要處理大量的set union
不如直接用bit operation來列出所有的解
以下取自rosetta code
http://rosettacode.org/wiki/Power_set


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

static void powerset(int argc, char** argv)
{
    unsigned int i, j, bits, i_max = 1U << argc;

    if (argc >= sizeof(i) * CHAR_BIT) {
        fprintf(stderr, "Error: set too large\n");
        exit(1);
    }

    for (i = 0; i < i_max ; ++i) {
        printf("{");
        for (bits = i, j = 0; bits; bits >>= 1, ++j) {
            if (bits & 1)
                printf(bits > 1 ? "%s, " : "%s", argv[j]);
        }
        printf("}\n");
    }
}

int main(int argc, char* argv[])
{
    powerset(argc - 1, argv + 1);
    return 0;
}

演算法很單純卻很有效，假設原本的set是array
{"a","b","c"}
我們要讓i從0累加到7，以二進位來看就是從000到111
一開始i為0
印出{}
i = 000         ==> {}
i = 001         ==> {a}
i = 010         ==> {b}
i = 011         ==> {a, b}  有兩個以上位元時，最內層for迴圈會把bit逐個
                            讀出來，利用bits>>=來位移，並用bits&1來檢測
i = 100         ==> {c}
i = 101         ==> {a, c}
i = 110         ==> {b, c}
i = 111         ==> {a, b, c}

這比遞迴有效得多...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.181.4.39
※ 編輯: dryman          來自: 68.181.4.39          (03/06 09:43)
推 loveme00835:推~