14134 - Strawhats' Bento Set

!!! Prof. Hu said to learn this problem !!!

Mechanism:

Ideas:

1. Use binary placement to create possible moves
2. Explore the moves through loop and mask

Problem

Take example, the set of Ingredients 1

Ingredients 1 = {'Rice','Salmon'}

Then, the bento sets he is going to make are {{'Rice'},{'Salmon'},{'Rice','Salmon'}

Here is another example set of ingredients 2

Ingredients 2 = {'Rice','Seaweed','Meat'}

Then the bento sets he is going to make are {{'Rice'},{'Seaweed'},{'Rice','Seaweed'},{'Meat'},{'Rice','Meat'},{'Seaweed','Meat'},{'Rice','Seaweed','Meat'}}

But Chopper is too lazy to write all the ingredients… So he decided to label everything into a single number or alphabet!!

The set of Ingredients 1 becomes {'1','2'}

and the bento sets are {{'1'},{'2'},{'1','2'}}

The set of Inredients 2 becomes {'1','2','a'}

and the bento sets are {{'1'},{'2'},{'1','2'},{'a'},{'1','a'},{'2','a'},{'1','2','a'}}

Now help Chopper list the bento sets by given a aspecific set of ingredients.

TLDR: 3a1 => 3, a, 1, 3a, a1, 31, 3a1 (but in ordered seq)

Input:
String I that can be viewed as a set

length of I , 4 < I < 21

Output:
Output the bento sets followed by a newline character at the end of each set

Sample:
3a1
Result:
3
a
3a
1
31
a1
3a1

Solution

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

int mask[24] = {
	0x000001, 0x000002, 0x000004, 0x000008, 
	0x000010, 0x000020, 0x000040, 0x000080,
	0x000100, 0x000200, 0x000400, 0x000800,
	0x001000, 0x002000, 0x004000, 0x008000,
	0x010000, 0x020000, 0x040000, 0x080000,
	0x100000, 0x200000, 0x400000, 0x800000
};

int main(void) {
	char set[21];
	scanf(" %s", set);
	
	int length = strlen(set);
	int lim = 1 << length; //Create the possible moves

	for(int i = 0; i < lim; i++){
		for(int j = 0; j < length; j++){
			if((i & mask[j]) != 0){
				printf("%c", set[j]);//If true, refer to the corresponding real value
			}
		}
		if(i > 0) printf("\n");
	}
  return 0;
}

Optimization by LewiSC

// Auto generate mask
  for (int i = 0; i < lim; i++) {
    for (int j = 0x1; j <= 0x8; j *= 0x2) {
      mask[cnt++] = j << (sizeof(int) * i);
      if (cnt >= lim) break;
    }
    if (cnt >= lim) break;
  }

  for (int i = 0; i < cnt; i++) {
		if(i % 4 == 0) printf("\n");
    printf("%X\t", mask[i]);
  }

//Practice
#include <stdio.h>
#include <string.h>

int main(void){
    char set[21];
    scanf(" %s", set);
    
    int len = strlen(set);
    int lim = 1 << len;
    
    //1. Mask
    int mask[lim];
    int ctr = 0;
    
    for(int i = 0; i < lim; i++){
        for(int j = 0x1; j <= 0x8; j *= 0x2){
            mask[ctr++] = j << (sizeof(int) * i);
            if(ctr >= lim) break;
        }
        if(ctr >= lim) break;
    }
    
    //2. Correspondent
    for(int i = 0; i < lim; i++){
        for(int j = 0; j < len; j++){
            if((i & mask[j]) != 0) printf("%c", set[j]);
        }
        if(i > 0) printf("\n");
    }
    
    return 0;
}