algorithm - 打印和存储给定数字的不同长度排列

Question

如果我有一个数字 2345，那么它会做什么打印：2 3 4 5 23 24 25 34 35 45 234 235 345

即打印所有可能的数字直到长度为1。？？？

Answer 1

#include <stdio.h>
#include <string.h>
#include <math.h>

int bitcount(long bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

void select(const char *src, char *select, unsigned int pattern){
    for(;pattern;++src, pattern >>= 1)
        if(pattern & 1)
            *select++ = *src;
    *select ='\0';
}

int main(){
    const char* selectList = "2345";
    char buff[sizeof(selectList)/sizeof(char)+1];
    int len = strlen(selectList);
    int max = pow(2, len) -1;
    int i, j;
    for(i = 1; i<len;++i){
        //j:bit pattern
        for(j = 1; j<max;++j){
            if(i==bitcount(j)){
                select(selectList, buff, j);
                printf("%s\n", buff);
            }
        }
    }
    return 0;
}

Answer 2

使用 depth-first-search(dfs) 你可以做到这一点，这是一个例子：

#include <cstdio>
#include <cstring>

char s[10];
char a[10];

void doSomething(char* s){
    printf("%s\n", s);
}

void dfs(int x, int y){
    if (!s[x]){
        a[y] = 0;
        doSomething(a);
        return;
    }
    dfs(x + 1, y);
    a[y] = s[x];
    dfs(x + 1, y + 1);
}

int main(){
    scanf("%s", s);
    dfs(0, 0);
    return 0;
}