수학의정석/집합의연산/이영호

No older revisions available

어렵다. 알고리즘 구현이 어렵다...
새로운 방법을 생각해내 구현을 하긴 했지만 배열을 malloc으로 했으면 더 좋았을걸이라는 생각이 계속 든다.
set 1-> a
set 2-> a

(a ab) b

set 3-> a ab b

(a ac) (ab, abc) (b, bc) c

set 4-> a ac ab abc b bc c

(a ad) (ac acd) (ab abd) (abc abcd) (b bd) (bc bcd) (c cd) d

가만히 보니 재귀호출을 생각해볼 수도 있었겠다.

set1에서는 a하나
set2에서는 set1과 set1+set2 set2
set3에서는 set2와 set2+set3 set3

이렇게 나가게된다.
이것을 아래에 구현 했다. 복잡하지만.

만약 이것을 malloc으로 구현하려했다면 메모리 크기를 구해야하므로
메모리의 크기는 Ssub(n) = 2Ssub(n-1) + asub(n-1) + 1 이 된다.
S -> 크기(메모리, 각각의 수의 갯수), a -> 항(subset)의 갯수

input은 9 {1,2,3,4,5,6,7,8,9}로 테스트를 해 보았다. 결과는 아래.
set9에서 0.03초 set10에서 0.12초, set12에서 2.4초가 나왔다.

~cpp 
#include <stdio.h>
#include <time.h>
#include <string.h>

int print(char *set, int size);

int main()
{
                int size;
                int i;
                clock_t time_in;
                scanf(" %d", &size);
                char set[size];
                time_in = clock();
                for(i=0; i<size; i++)
                                scanf(" %d", &(set[i]));

                print(set, size);
                printf("CLOCK_TIME = %d\n", clock() - time_in);

                return 0;
}

int print(char *set, int size)
{
                int count;
                int i, j, t;
                char buf[3000];
                char temp[3000];
                char next;

                for(i = 1; i <= size; i++){
                                next = set[i-1];

                                if(next == '\0') break;

                                if(i == 1){
                                                buf[0] = next;
                                                buf[1] = '\0';
                                                continue;
                                }

                                for(j = 0, count = 0; buf[j] != '\0';){
                                                if(buf[j] == 99){
                                                                temp[count++] = 99;
                                                                j++;
                                                }
                                                else{
                                                                for(t = 0; buf[j+t] != 99 && buf[j+t] != '\0'; t++)
                                                                                temp[count++] = buf[j+t];
                                                                temp[count++] = 99;
                                                                for(t = 0; buf[j+t] != 99 && buf[j+t] != '\0'; t++)
                                                                                temp[count++] = buf[j+t];
                                                                temp[count++] = next;
                                                                j+=t;
                                                }
                                }
                                                                temp[count++] = 99;
                                temp[count++] = next;
                                temp[count] = '\0';
                                memcpy(buf, temp, strlen(temp));
                                buf[strlen(temp)] = '\0';
                }

                                printf("{");
                for(i = 0; i < strlen(buf); i++){
                                if(buf[i] == 99)
                                                printf("\b},{");
                                else if(buf[i] == '\0')
                                                break;
                                else
                                                printf("%d,", buf[i]);
                }
                                printf("\b}\n");

                return 0;
}

subset 들. set은 {1,2,3,4,5,6,7,8,9}이다.
갯수는 2^9 - 1로 511개.
{1},{1,9},{1,8},{1,8,9},{1,7},{1,7,9},{1,7,8},{1,7,8,9},{1,6},{1,6,9},{1,6,8},{1,6,8,9},{1,6,7},{1,6,7,9},{1,6,7,8},{1,6,7,8,9},{1,5},{1,5,9},{1,5,8},{1,5,8,9},{1,5,7},{1,5,7,9},{1,5,7,8},{1,5,7,8,9},{1,5,6},{1,5,6,9},{1,5,6,8},{1,5,6,8,9},{1,5,6,7},{1,5,6,7,9},{1,5,6,7,8},{1,5,6,7,8,9},{1,4},{1,4,9},{1,4,8},{1,4,8,9},{1,4,7},{1,4,7,9},{1,4,7,8},{1,4,7,8,9},{1,4,6},{1,4,6,9},{1,4,6,8},{1,4,6,8,9},{1,4,6,7},{1,4,6,7,9},{1,4,6,7,8},{1,4,6,7,8,9},{1,4,5},{1,4,5,9},{1,4,5,8},{1,4,5,8,9},{1,4,5,7},{1,4,5,7,9},{1,4,5,7,8},{1,4,5,7,8,9},{1,4,5,6},{1,4,5,6,9},{1,4,5,6,8},{1,4,5,6,8,9},{1,4,5,6,7},{1,4,5,6,7,9},{1,4,5,6,7,8},{1,4,5,6,7,8,9},{1,3},{1,3,9},{1,3,8},{1,3,8,9},{1,3,7},{1,3,7,9},{1,3,7,8},{1,3,7,8,9},{1,3,6},{1,3,6,9},{1,3,6,8},{1,3,6,8,9},{1,3,6,7},{1,3,6,7,9},{1,3,6,7,8},{1,3,6,7,8,9},{1,3,5},{1,3,5,9},{1,3,5,8},{1,3,5,8,9},{1,3,5,7},{1,3,5,7,9},{1,3,5,7,8},{1,3,5,7,8,9},{1,3,5,6},{1,3,5,6,9},{1,3,5,6,8},{1,3,5,6,8,9},{1,3,5,6,7},{1,3,5,6,7,9},{1,3,5,6,7,8},{1,3,5,6,7,8,9},{1,3,4},{1,3,4,9},{1,3,4,8},{1,3,4,8,9},{1,3,4,7},{1,3,4,7,9},{1,3,4,7,8},{1,3,4,7,8,9},{1,3,4,6},{1,3,4,6,9},{1,3,4,6,8},{1,3,4,6,8,9},{1,3,4,6,7},{1,3,4,6,7,9},{1,3,4,6,7,8},{1,3,4,6,7,8,9},{1,3,4,5},{1,3,4,5,9},{1,3,4,5,8},{1,3,4,5,8,9},{1,3,4,5,7},{1,3,4,5,7,9},{1,3,4,5,7,8},{1,3,4,5,7,8,9},{1,3,4,5,6},{1,3,4,5,6,9},{1,3,4,5,6,8},{1,3,4,5,6,8,9},{1,3,4,5,6,7},{1,3,4,5,6,7,9},{1,3,4,5,6,7,8},{1,3,4,5,6,7,8,9},{1,2},{1,2,9},{1,2,8},{1,2,8,9},{1,2,7},{1,2,7,9},{1,2,7,8},{1,2,7,8,9},{1,2,6},{1,2,6,9},{1,2,6,8},{1,2,6,8,9},{1,2,6,7},{1,2,6,7,9},{1,2,6,7,8},{1,2,6,7,8,9},{1,2,5},{1,2,5,9},{1,2,5,8},{1,2,5,8,9},{1,2,5,7},{1,2,5,7,9},{1,2,5,7,8},{1,2,5,7,8,9},{1,2,5,6},{1,2,5,6,9},{1,2,5,6,8},{1,2,5,6,8,9},{1,2,5,6,7},{1,2,5,6,7,9},{1,2,5,6,7,8},{1,2,5,6,7,8,9},{1,2,4},{1,2,4,9},{1,2,4,8},{1,2,4,8,9},{1,2,4,7},{1,2,4,7,9},{1,2,4,7,8},{1,2,4,7,8,9},{1,2,4,6},{1,2,4,6,9},{1,2,4,6,8},{1,2,4,6,8,9},{1,2,4,6,7},{1,2,4,6,7,9},{1,2,4,6,7,8},{1,2,4,6,7,8,9},{1,2,4,5},{1,2,4,5,9},{1,2,4,5,8},{1,2,4,5,8,9},{1,2,4,5,7},{1,2,4,5,7,9},{1,2,4,5,7,8},{1,2,4,5,7,8,9},{1,2,4,5,6},{1,2,4,5,6,9},{1,2,4,5,6,8},{1,2,4,5,6,8,9},{1,2,4,5,6,7},{1,2,4,5,6,7,9},{1,2,4,5,6,7,8},{1,2,4,5,6,7,8,9},{1,2,3},{1,2,3,9},{1,2,3,8},{1,2,3,8,9},{1,2,3,7},{1,2,3,7,9},{1,2,3,7,8},{1,2,3,7,8,9},{1,2,3,6},{1,2,3,6,9},{1,2,3,6,8},{1,2,3,6,8,9},{1,2,3,6,7},{1,2,3,6,7,9},{1,2,3,6,7,8},{1,2,3,6,7,8,9},{1,2,3,5},{1,2,3,5,9},{1,2,3,5,8},{1,2,3,5,8,9},{1,2,3,5,7},{1,2,3,5,7,9},{1,2,3,5,7,8},{1,2,3,5,7,8,9},{1,2,3,5,6},{1,2,3,5,6,9},{1,2,3,5,6,8},{1,2,3,5,6,8,9},{1,2,3,5,6,7},{1,2,3,5,6,7,9},{1,2,3,5,6,7,8},{1,2,3,5,6,7,8,9},{1,2,3,4},{1,2,3,4,9},{1,2,3,4,8},{1,2,3,4,8,9},{1,2,3,4,7},{1,2,3,4,7,9},{1,2,3,4,7,8},{1,2,3,4,7,8,9},{1,2,3,4,6},{1,2,3,4,6,9},{1,2,3,4,6,8},{1,2,3,4,6,8,9},{1,2,3,4,6,7},{1,2,3,4,6,7,9},{1,2,3,4,6,7,8},{1,2,3,4,6,7,8,9},{1,2,3,4,5},{1,2,3,4,5,9},{1,2,3,4,5,8},{1,2,3,4,5,8,9},{1,2,3,4,5,7},{1,2,3,4,5,7,9},{1,2,3,4,5,7,8},{1,2,3,4,5,7,8,9},{1,2,3,4,5,6},{1,2,3,4,5,6,9},{1,2,3,4,5,6,8},{1,2,3,4,5,6,8,9},{1,2,3,4,5,6,7},{1,2,3,4,5,6,7,9},{1,2,3,4,5,6,7,8},{1,2,3,4,5,6,7,8,9},{2},{2,9},{2,8},{2,8,9},{2,7},{2,7,9},{2,7,8},{2,7,8,9},{2,6},{2,6,9},{2,6,8},{2,6,8,9},{2,6,7},{2,6,7,9},{2,6,7,8},{2,6,7,8,9},{2,5},{2,5,9},{2,5,8},{2,5,8,9},{2,5,7},{2,5,7,9},{2,5,7,8},{2,5,7,8,9},{2,5,6},{2,5,6,9},{2,5,6,8},{2,5,6,8,9},{2,5,6,7},{2,5,6,7,9},{2,5,6,7,8},{2,5,6,7,8,9},{2,4},{2,4,9},{2,4,8},{2,4,8,9},{2,4,7},{2,4,7,9},{2,4,7,8},{2,4,7,8,9},{2,4,6},{2,4,6,9},{2,4,6,8},{2,4,6,8,9},{2,4,6,7},{2,4,6,7,9},{2,4,6,7,8},{2,4,6,7,8,9},{2,4,5},{2,4,5,9},{2,4,5,8},{2,4,5,8,9},{2,4,5,7},{2,4,5,7,9},{2,4,5,7,8},{2,4,5,7,8,9},{2,4,5,6},{2,4,5,6,9},{2,4,5,6,8},{2,4,5,6,8,9},{2,4,5,6,7},{2,4,5,6,7,9},{2,4,5,6,7,8},{2,4,5,6,7,8,9},{2,3},{2,3,9},{2,3,8},{2,3,8,9},{2,3,7},{2,3,7,9},{2,3,7,8},{2,3,7,8,9},{2,3,6},{2,3,6,9},{2,3,6,8},{2,3,6,8,9},{2,3,6,7},{2,3,6,7,9},{2,3,6,7,8},{2,3,6,7,8,9},{2,3,5},{2,3,5,9},{2,3,5,8},{2,3,5,8,9},{2,3,5,7},{2,3,5,7,9},{2,3,5,7,8},{2,3,5,7,8,9},{2,3,5,6},{2,3,5,6,9},{2,3,5,6,8},{2,3,5,6,8,9},{2,3,5,6,7},{2,3,5,6,7,9},{2,3,5,6,7,8},{2,3,5,6,7,8,9},{2,3,4},{2,3,4,9},{2,3,4,8},{2,3,4,8,9},{2,3,4,7},{2,3,4,7,9},{2,3,4,7,8},{2,3,4,7,8,9},{2,3,4,6},{2,3,4,6,9},{2,3,4,6,8},{2,3,4,6,8,9},{2,3,4,6,7},{2,3,4,6,7,9},{2,3,4,6,7,8},{2,3,4,6,7,8,9},{2,3,4,5},{2,3,4,5,9},{2,3,4,5,8},{2,3,4,5,8,9},{2,3,4,5,7},{2,3,4,5,7,9},{2,3,4,5,7,8},{2,3,4,5,7,8,9},{2,3,4,5,6},{2,3,4,5,6,9},{2,3,4,5,6,8},{2,3,4,5,6,8,9},{2,3,4,5,6,7},{2,3,4,5,6,7,9},{2,3,4,5,6,7,8},{2,3,4,5,6,7,8,9},{3},{3,9},{3,8},{3,8,9},{3,7},{3,7,9},{3,7,8},{3,7,8,9},{3,6},{3,6,9},{3,6,8},{3,6,8,9},{3,6,7},{3,6,7,9},{3,6,7,8},{3,6,7,8,9},{3,5},{3,5,9},{3,5,8},{3,5,8,9},{3,5,7},{3,5,7,9},{3,5,7,8},{3,5,7,8,9},{3,5,6},{3,5,6,9},{3,5,6,8},{3,5,6,8,9},{3,5,6,7},{3,5,6,7,9},{3,5,6,7,8},{3,5,6,7,8,9},{3,4},{3,4,9},{3,4,8},{3,4,8,9},{3,4,7},{3,4,7,9},{3,4,7,8},{3,4,7,8,9},{3,4,6},{3,4,6,9},{3,4,6,8},{3,4,6,8,9},{3,4,6,7},{3,4,6,7,9},{3,4,6,7,8},{3,4,6,7,8,9},{3,4,5},{3,4,5,9},{3,4,5,8},{3,4,5,8,9},{3,4,5,7},{3,4,5,7,9},{3,4,5,7,8},{3,4,5,7,8,9},{3,4,5,6},{3,4,5,6,9},{3,4,5,6,8},{3,4,5,6,8,9},{3,4,5,6,7},{3,4,5,6,7,9},{3,4,5,6,7,8},{3,4,5,6,7,8,9},{4},{4,9},{4,8},{4,8,9},{4,7},{4,7,9},{4,7,8},{4,7,8,9},{4,6},{4,6,9},{4,6,8},{4,6,8,9},{4,6,7},{4,6,7,9},{4,6,7,8},{4,6,7,8,9},{4,5},{4,5,9},{4,5,8},{4,5,8,9},{4,5,7},{4,5,7,9},{4,5,7,8},{4,5,7,8,9},{4,5,6},{4,5,6,9},{4,5,6,8},{4,5,6,8,9},{4,5,6,7},{4,5,6,7,9},{4,5,6,7,8},{4,5,6,7,8,9},{5},{5,9},{5,8},{5,8,9},{5,7},{5,7,9},{5,7,8},{5,7,8,9},{5,6},{5,6,9},{5,6,8},{5,6,8,9},{5,6,7},{5,6,7,9},{5,6,7,8},{5,6,7,8,9},{6},{6,9},{6,8},{6,8,9},{6,7},{6,7,9},{6,7,8},{6,7,8,9},{7},{7,9},{7,8},{7,8,9},{8},{8,9},{9}

subset 들. set은 {1,2,3,4,5,6,7,8,9,10}이다.
갯수는 2^19 - 1로 1023개.
{1},{1,10},{1,9},{1,9,10},{1,8},{1,8,10},{1,8,9},{1,8,9,10},{1,7},{1,7,10},{1,7,9},{1,7,9,10},{1,7,8},{1,7,8,10},{1,7,8,9},{1,7,8,9,10},{1,6},{1,6,10},{1,6,9},{1,6,9,10},{1,6,8},{1,6,8,10},{1,6,8,9},{1,6,8,9,10},{1,6,7},{1,6,7,10},{1,6,7,9},{1,6,7,9,10},{1,6,7,8},{1,6,7,8,10},{1,6,7,8,9},{1,6,7,8,9,10},{1,5},{1,5,10},{1,5,9},{1,5,9,10},{1,5,8},{1,5,8,10},{1,5,8,9},{1,5,8,9,10},{1,5,7},{1,5,7,10},{1,5,7,9},{1,5,7,9,10},{1,5,7,8},{1,5,7,8,10},{1,5,7,8,9},{1,5,7,8,9,10},{1,5,6},{1,5,6,10},{1,5,6,9},{1,5,6,9,10},{1,5,6,8},{1,5,6,8,10},{1,5,6,8,9},{1,5,6,8,9,10},{1,5,6,7},{1,5,6,7,10},{1,5,6,7,9},{1,5,6,7,9,10},{1,5,6,7,8},{1,5,6,7,8,10},{1,5,6,7,8,9},{1,5,6,7,8,9,10},{1,4},{1,4,10},{1,4,9},{1,4,9,10},{1,4,8},{1,4,8,10},{1,4,8,9},{1,4,8,9,10},{1,4,7},{1,4,7,10},{1,4,7,9},{1,4,7,9,10},{1,4,7,8},{1,4,7,8,10},{1,4,7,8,9},{1,4,7,8,9,10},{1,4,6},{1,4,6,10},{1,4,6,9},{1,4,6,9,10},{1,4,6,8},{1,4,6,8,10},{1,4,6,8,9},{1,4,6,8,9,10},{1,4,6,7},{1,4,6,7,10},{1,4,6,7,9},{1,4,6,7,9,10},{1,4,6,7,8},{1,4,6,7,8,10},{1,4,6,7,8,9},{1,4,6,7,8,9,10},{1,4,5},{1,4,5,10},{1,4,5,9},{1,4,5,9,10},{1,4,5,8},{1,4,5,8,10},{1,4,5,8,9},{1,4,5,8,9,10},{1,4,5,7},{1,4,5,7,10},{1,4,5,7,9},{1,4,5,7,9,10},{1,4,5,7,8},{1,4,5,7,8,10},{1,4,5,7,8,9},{1,4,5,7,8,9,10},{1,4,5,6},{1,4,5,6,10},{1,4,5,6,9},{1,4,5,6,9,10},{1,4,5,6,8},{1,4,5,6,8,10},{1,4,5,6,8,9},{1,4,5,6,8,9,10},{1,4,5,6,7},{1,4,5,6,7,10},{1,4,5,6,7,9},{1,4,5,6,7,9,10},{1,4,5,6,7,8},{1,4,5,6,7,8,10},{1,4,5,6,7,8,9},{1,4,5,6,7,8,9,10},{1,3},{1,3,10},{1,3,9},{1,3,9,10},{1,3,8},{1,3,8,10},{1,3,8,9},{1,3,8,9,10},{1,3,7},{1,3,7,10},{1,3,7,9},{1,3,7,9,10},{1,3,7,8},{1,3,7,8,10},{1,3,7,8,9},{1,3,7,8,9,10},{1,3,6},{1,3,6,10},{1,3,6,9},{1,3,6,9,10},{1,3,6,8},{1,3,6,8,10},{1,3,6,8,9},{1,3,6,8,9,10},{1,3,6,7},{1,3,6,7,10},{1,3,6,7,9},{1,3,6,7,9,10},{1,3,6,7,8},{1,3,6,7,8,10},{1,3,6,7,8,9},{1,3,6,7,8,9,10},{1,3,5},{1,3,5,10},{1,3,5,9},{1,3,5,9,10},{1,3,5,8},{1,3,5,8,10},{1,3,5,8,9},{1,3,5,8,9,10},{1,3,5,7},{1,3,5,7,10},{1,3,5,7,9},{1,3,5,7,9,10},{1,3,5,7,8},{1,3,5,7,8,10},{1,3,5,7,8,9},{1,3,5,7,8,9,10},{1,3,5,6},{1,3,5,6,10},{1,3,5,6,9},{1,3,5,6,9,10},{1,3,5,6,8},{1,3,5,6,8,10},{1,3,5,6,8,9},{1,3,5,6,8,9,10},{1,3,5,6,7},{1,3,5,6,7,10},{1,3,5,6,7,9},{1,3,5,6,7,9,10},{1,3,5,6,7,8},{1,3,5,6,7,8,10},{1,3,5,6,7,8,9},{1,3,5,6,7,8,9,10},{1,3,4},{1,3,4,10},{1,3,4,9},{1,3,4,9,10},{1,3,4,8},{1,3,4,8,10},{1,3,4,8,9},{1,3,4,8,9,10},{1,3,4,7},{1,3,4,7,10},{1,3,4,7,9},{1,3,4,7,9,10},{1,3,4,7,8},{1,3,4,7,8,10},{1,3,4,7,8,9},{1,3,4,7,8,9,10},{1,3,4,6},{1,3,4,6,10},{1,3,4,6,9},{1,3,4,6,9,10},{1,3,4,6,8},{1,3,4,6,8,10},{1,3,4,6,8,9},{1,3,4,6,8,9,10},{1,3,4,6,7},{1,3,4,6,7,10},{1,3,4,6,7,9},{1,3,4,6,7,9,10},{1,3,4,6,7,8},{1,3,4,6,7,8,10},{1,3,4,6,7,8,9},{1,3,4,6,7,8,9,10},{1,3,4,5},{1,3,4,5,10},{1,3,4,5,9},{1,3,4,5,9,10},{1,3,4,5,8},{1,3,4,5,8,10},{1,3,4,5,8,9},{1,3,4,5,8,9,10},{1,3,4,5,7},{1,3,4,5,7,10},{1,3,4,5,7,9},{1,3,4,5,7,9,10},{1,3,4,5,7,8},{1,3,4,5,7,8,10},{1,3,4,5,7,8,9},{1,3,4,5,7,8,9,10},{1,3,4,5,6},{1,3,4,5,6,10},{1,3,4,5,6,9},{1,3,4,5,6,9,10},{1,3,4,5,6,8},{1,3,4,5,6,8,10},{1,3,4,5,6,8,9},{1,3,4,5,6,8,9,10},{1,3,4,5,6,7},{1,3,4,5,6,7,10},{1,3,4,5,6,7,9},{1,3,4,5,6,7,9,10},{1,3,4,5,6,7,8},{1,3,4,5,6,7,8,10},{1,3,4,5,6,7,8,9},{1,3,4,5,6,7,8,9,10},{1,2},{1,2,10},{1,2,9},{1,2,9,10},{1,2,8},{1,2,8,10},{1,2,8,9},{1,2,8,9,10},{1,2,7},{1,2,7,10},{1,2,7,9},{1,2,7,9,10},{1,2,7,8},{1,2,7,8,10},{1,2,7,8,9},{1,2,7,8,9,10},{1,2,6},{1,2,6,10},{1,2,6,9},{1,2,6,9,10},{1,2,6,8},{1,2,6,8,10},{1,2,6,8,9},{1,2,6,8,9,10},{1,2,6,7},{1,2,6,7,10},{1,2,6,7,9},{1,2,6,7,9,10},{1,2,6,7,8},{1,2,6,7,8,10},{1,2,6,7,8,9},{1,2,6,7,8,9,10},{1,2,5},{1,2,5,10},{1,2,5,9},{1,2,5,9,10},{1,2,5,8},{1,2,5,8,10},{1,2,5,8,9},{1,2,5,8,9,10},{1,2,5,7},{1,2,5,7,10},{1,2,5,7,9},{1,2,5,7,9,10},{1,2,5,7,8},{1,2,5,7,8,10},{1,2,5,7,8,9},{1,2,5,7,8,9,10},{1,2,5,6},{1,2,5,6,10},{1,2,5,6,9},{1,2,5,6,9,10},{1,2,5,6,8},{1,2,5,6,8,10},{1,2,5,6,8,9},{1,2,5,6,8,9,10},{1,2,5,6,7},{1,2,5,6,7,10},{1,2,5,6,7,9},{1,2,5,6,7,9,10},{1,2,5,6,7,8},{1,2,5,6,7,8,10},{1,2,5,6,7,8,9},{1,2,5,6,7,8,9,10},{1,2,4},{1,2,4,10},{1,2,4,9},{1,2,4,9,10},{1,2,4,8},{1,2,4,8,10},{1,2,4,8,9},{1,2,4,8,9,10},{1,2,4,7},{1,2,4,7,10},{1,2,4,7,9},{1,2,4,7,9,10},{1,2,4,7,8},{1,2,4,7,8,10},{1,2,4,7,8,9},{1,2,4,7,8,9,10},{1,2,4,6},{1,2,4,6,10},{1,2,4,6,9},{1,2,4,6,9,10},{1,2,4,6,8},{1,2,4,6,8,10},{1,2,4,6,8,9},{1,2,4,6,8,9,10},{1,2,4,6,7},{1,2,4,6,7,10},{1,2,4,6,7,9},{1,2,4,6,7,9,10},{1,2,4,6,7,8},{1,2,4,6,7,8,10},{1,2,4,6,7,8,9},{1,2,4,6,7,8,9,10},{1,2,4,5},{1,2,4,5,10},{1,2,4,5,9},{1,2,4,5,9,10},{1,2,4,5,8},{1,2,4,5,8,10},{1,2,4,5,8,9},{1,2,4,5,8,9,10},{1,2,4,5,7},{1,2,4,5,7,10},{1,2,4,5,7,9},{1,2,4,5,7,9,10},{1,2,4,5,7,8},{1,2,4,5,7,8,10},{1,2,4,5,7,8,9},{1,2,4,5,7,8,9,10},{1,2,4,5,6},{1,2,4,5,6,10},{1,2,4,5,6,9},{1,2,4,5,6,9,10},{1,2,4,5,6,8},{1,2,4,5,6,8,10},{1,2,4,5,6,8,9},{1,2,4,5,6,8,9,10},{1,2,4,5,6,7},{1,2,4,5,6,7,10},{1,2,4,5,6,7,9},{1,2,4,5,6,7,9,10},{1,2,4,5,6,7,8},{1,2,4,5,6,7,8,10},{1,2,4,5,6,7,8,9},{1,2,4,5,6,7,8,9,10},{1,2,3},{1,2,3,10},{1,2,3,9},{1,2,3,9,10},{1,2,3,8},{1,2,3,8,10},{1,2,3,8,9},{1,2,3,8,9,10},{1,2,3,7},{1,2,3,7,10},{1,2,3,7,9},{1,2,3,7,9,10},{1,2,3,7,8},{1,2,3,7,8,10},{1,2,3,7,8,9},{1,2,3,7,8,9,10},{1,2,3,6},{1,2,3,6,10},{1,2,3,6,9},{1,2,3,6,9,10},{1,2,3,6,8},{1,2,3,6,8,10},{1,2,3,6,8,9},{1,2,3,6,8,9,10},{1,2,3,6,7},{1,2,3,6,7,10},{1,2,3,6,7,9},{1,2,3,6,7,9,10},{1,2,3,6,7,8},{1,2,3,6,7,8,10},{1,2,3,6,7,8,9},{1,2,3,6,7,8,9,10},{1,2,3,5},{1,2,3,5,10},{1,2,3,5,9},{1,2,3,5,9,10},{1,2,3,5,8},{1,2,3,5,8,10},{1,2,3,5,8,9},{1,2,3,5,8,9,10},{1,2,3,5,7},{1,2,3,5,7,10},{1,2,3,5,7,9},{1,2,3,5,7,9,10},{1,2,3,5,7,8},{1,2,3,5,7,8,10},{1,2,3,5,7,8,9},{1,2,3,5,7,8,9,10},{1,2,3,5,6},{1,2,3,5,6,10},{1,2,3,5,6,9},{1,2,3,5,6,9,10},{1,2,3,5,6,8},{1,2,3,5,6,8,10},{1,2,3,5,6,8,9},{1,2,3,5,6,8,9,10},{1,2,3,5,6,7},{1,2,3,5,6,7,10},{1,2,3,5,6,7,9},{1,2,3,5,6,7,9,10},{1,2,3,5,6,7,8},{1,2,3,5,6,7,8,10},{1,2,3,5,6,7,8,9},{1,2,3,5,6,7,8,9,10},{1,2,3,4},{1,2,3,4,10},{1,2,3,4,9},{1,2,3,4,9,10},{1,2,3,4,8},{1,2,3,4,8,10},{1,2,3,4,8,9},{1,2,3,4,8,9,10},{1,2,3,4,7},{1,2,3,4,7,10},{1,2,3,4,7,9},{1,2,3,4,7,9,10},{1,2,3,4,7,8},{1,2,3,4,7,8,10},{1,2,3,4,7,8,9},{1,2,3,4,7,8,9,10},{1,2,3,4,6},{1,2,3,4,6,10},{1,2,3,4,6,9},{1,2,3,4,6,9,10},{1,2,3,4,6,8},{1,2,3,4,6,8,10},{1,2,3,4,6,8,9},{1,2,3,4,6,8,9,10},{1,2,3,4,6,7},{1,2,3,4,6,7,10},{1,2,3,4,6,7,9},{1,2,3,4,6,7,9,10},{1,2,3,4,6,7,8},{1,2,3,4,6,7,8,10},{1,2,3,4,6,7,8,9},{1,2,3,4,6,7,8,9,10},{1,2,3,4,5},{1,2,3,4,5,10},{1,2,3,4,5,9},{1,2,3,4,5,9,10},{1,2,3,4,5,8},{1,2,3,4,5,8,10},{1,2,3,4,5,8,9},{1,2,3,4,5,8,9,10},{1,2,3,4,5,7},{1,2,3,4,5,7,10},{1,2,3,4,5,7,9},{1,2,3,4,5,7,9,10},{1,2,3,4,5,7,8},{1,2,3,4,5,7,8,10},{1,2,3,4,5,7,8,9},{1,2,3,4,5,7,8,9,10},{1,2,3,4,5,6},{1,2,3,4,5,6,10},{1,2,3,4,5,6,9},{1,2,3,4,5,6,9,10},{1,2,3,4,5,6,8},{1,2,3,4,5,6,8,10},{1,2,3,4,5,6,8,9},{1,2,3,4,5,6,8,9,10},{1,2,3,4,5,6,7},{1,2,3,4,5,6,7,10},{1,2,3,4,5,6,7,9},{1,2,3,4,5,6,7,9,10},{1,2,3,4,5,6,7,8},{1,2,3,4,5,6,7,8,10},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9,10},{2},{2,10},{2,9},{2,9,10},{2,8},{2,8,10},{2,8,9},{2,8,9,10},{2,7},{2,7,10},{2,7,9},{2,7,9,10},{2,7,8},{2,7,8,10},{2,7,8,9},{2,7,8,9,10},{2,6},{2,6,10},{2,6,9},{2,6,9,10},{2,6,8},{2,6,8,10},{2,6,8,9},{2,6,8,9,10},{2,6,7},{2,6,7,10},{2,6,7,9},{2,6,7,9,10},{2,6,7,8},{2,6,7,8,10},{2,6,7,8,9},{2,6,7,8,9,10},{2,5},{2,5,10},{2,5,9},{2,5,9,10},{2,5,8},{2,5,8,10},{2,5,8,9},{2,5,8,9,10},{2,5,7},{2,5,7,10},{2,5,7,9},{2,5,7,9,10},{2,5,7,8},{2,5,7,8,10},{2,5,7,8,9},{2,5,7,8,9,10},{2,5,6},{2,5,6,10},{2,5,6,9},{2,5,6,9,10},{2,5,6,8},{2,5,6,8,10},{2,5,6,8,9},{2,5,6,8,9,10},{2,5,6,7},{2,5,6,7,10},{2,5,6,7,9},{2,5,6,7,9,10},{2,5,6,7,8},{2,5,6,7,8,10},{2,5,6,7,8,9},{2,5,6,7,8,9,10},{2,4},{2,4,10},{2,4,9},{2,4,9,10},{2,4,8},{2,4,8,10},{2,4,8,9},{2,4,8,9,10},{2,4,7},{2,4,7,10},{2,4,7,9},{2,4,7,9,10},{2,4,7,8},{2,4,7,8,10},{2,4,7,8,9},{2,4,7,8,9,10},{2,4,6},{2,4,6,10},{2,4,6,9},{2,4,6,9,10},{2,4,6,8},{2,4,6,8,10},{2,4,6,8,9},{2,4,6,8,9,10},{2,4,6,7},{2,4,6,7,10},{2,4,6,7,9},{2,4,6,7,9,10},{2,4,6,7,8},{2,4,6,7,8,10},{2,4,6,7,8,9},{2,4,6,7,8,9,10},{2,4,5},{2,4,5,10},{2,4,5,9},{2,4,5,9,10},{2,4,5,8},{2,4,5,8,10},{2,4,5,8,9},{2,4,5,8,9,10},{2,4,5,7},{2,4,5,7,10},{2,4,5,7,9},{2,4,5,7,9,10},{2,4,5,7,8},{2,4,5,7,8,10},{2,4,5,7,8,9},{2,4,5,7,8,9,10},{2,4,5,6},{2,4,5,6,10},{2,4,5,6,9},{2,4,5,6,9,10},{2,4,5,6,8},{2,4,5,6,8,10},{2,4,5,6,8,9},{2,4,5,6,8,9,10},{2,4,5,6,7},{2,4,5,6,7,10},{2,4,5,6,7,9},{2,4,5,6,7,9,10},{2,4,5,6,7,8},{2,4,5,6,7,8,10},{2,4,5,6,7,8,9},{2,4,5,6,7,8,9,10},{2,3},{2,3,10},{2,3,9},{2,3,9,10},{2,3,8},{2,3,8,10},{2,3,8,9},{2,3,8,9,10},{2,3,7},{2,3,7,10},{2,3,7,9},{2,3,7,9,10},{2,3,7,8},{2,3,7,8,10},{2,3,7,8,9},{2,3,7,8,9,10},{2,3,6},{2,3,6,10},{2,3,6,9},{2,3,6,9,10},{2,3,6,8},{2,3,6,8,10},{2,3,6,8,9},{2,3,6,8,9,10},{2,3,6,7},{2,3,6,7,10},{2,3,6,7,9},{2,3,6,7,9,10},{2,3,6,7,8},{2,3,6,7,8,10},{2,3,6,7,8,9},{2,3,6,7,8,9,10},{2,3,5},{2,3,5,10},{2,3,5,9},{2,3,5,9,10},{2,3,5,8},{2,3,5,8,10},{2,3,5,8,9},{2,3,5,8,9,10},{2,3,5,7},{2,3,5,7,10},{2,3,5,7,9},{2,3,5,7,9,10},{2,3,5,7,8},{2,3,5,7,8,10},{2,3,5,7,8,9},{2,3,5,7,8,9,10},{2,3,5,6},{2,3,5,6,10},{2,3,5,6,9},{2,3,5,6,9,10},{2,3,5,6,8},{2,3,5,6,8,10},{2,3,5,6,8,9},{2,3,5,6,8,9,10},{2,3,5,6,7},{2,3,5,6,7,10},{2,3,5,6,7,9},{2,3,5,6,7,9,10},{2,3,5,6,7,8},{2,3,5,6,7,8,10},{2,3,5,6,7,8,9},{2,3,5,6,7,8,9,10},{2,3,4},{2,3,4,10},{2,3,4,9},{2,3,4,9,10},{2,3,4,8},{2,3,4,8,10},{2,3,4,8,9},{2,3,4,8,9,10},{2,3,4,7},{2,3,4,7,10},{2,3,4,7,9},{2,3,4,7,9,10},{2,3,4,7,8},{2,3,4,7,8,10},{2,3,4,7,8,9},{2,3,4,7,8,9,10},{2,3,4,6},{2,3,4,6,10},{2,3,4,6,9},{2,3,4,6,9,10},{2,3,4,6,8},{2,3,4,6,8,10},{2,3,4,6,8,9},{2,3,4,6,8,9,10},{2,3,4,6,7},{2,3,4,6,7,10},{2,3,4,6,7,9},{2,3,4,6,7,9,10},{2,3,4,6,7,8},{2,3,4,6,7,8,10},{2,3,4,6,7,8,9},{2,3,4,6,7,8,9,10},{2,3,4,5},{2,3,4,5,10},{2,3,4,5,9},{2,3,4,5,9,10},{2,3,4,5,8},{2,3,4,5,8,10},{2,3,4,5,8,9},{2,3,4,5,8,9,10},{2,3,4,5,7},{2,3,4,5,7,10},{2,3,4,5,7,9},{2,3,4,5,7,9,10},{2,3,4,5,7,8},{2,3,4,5,7,8,10},{2,3,4,5,7,8,9},{2,3,4,5,7,8,9,10},{2,3,4,5,6},{2,3,4,5,6,10},{2,3,4,5,6,9},{2,3,4,5,6,9,10},{2,3,4,5,6,8},{2,3,4,5,6,8,10},{2,3,4,5,6,8,9},{2,3,4,5,6,8,9,10},{2,3,4,5,6,7},{2,3,4,5,6,7,10},{2,3,4,5,6,7,9},{2,3,4,5,6,7,9,10},{2,3,4,5,6,7,8},{2,3,4,5,6,7,8,10},{2,3,4,5,6,7,8,9},{2,3,4,5,6,7,8,9,10},{3},{3,10},{3,9},{3,9,10},{3,8},{3,8,10},{3,8,9},{3,8,9,10},{3,7},{3,7,10},{3,7,9},{3,7,9,10},{3,7,8},{3,7,8,10},{3,7,8,9},{3,7,8,9,10},{3,6},{3,6,10},{3,6,9},{3,6,9,10},{3,6,8},{3,6,8,10},{3,6,8,9},{3,6,8,9,10},{3,6,7},{3,6,7,10},{3,6,7,9},{3,6,7,9,10},{3,6,7,8},{3,6,7,8,10},{3,6,7,8,9},{3,6,7,8,9,10},{3,5},{3,5,10},{3,5,9},{3,5,9,10},{3,5,8},{3,5,8,10},{3,5,8,9},{3,5,8,9,10},{3,5,7},{3,5,7,10},{3,5,7,9},{3,5,7,9,10},{3,5,7,8},{3,5,7,8,10},{3,5,7,8,9},{3,5,7,8,9,10},{3,5,6},{3,5,6,10},{3,5,6,9},{3,5,6,9,10},{3,5,6,8},{3,5,6,8,10},{3,5,6,8,9},{3,5,6,8,9,10},{3,5,6,7},{3,5,6,7,10},{3,5,6,7,9},{3,5,6,7,9,10},{3,5,6,7,8},{3,5,6,7,8,10},{3,5,6,7,8,9},{3,5,6,7,8,9,10},{3,4},{3,4,10},{3,4,9},{3,4,9,10},{3,4,8},{3,4,8,10},{3,4,8,9},{3,4,8,9,10},{3,4,7},{3,4,7,10},{3,4,7,9},{3,4,7,9,10},{3,4,7,8},{3,4,7,8,10},{3,4,7,8,9},{3,4,7,8,9,10},{3,4,6},{3,4,6,10},{3,4,6,9},{3,4,6,9,10},{3,4,6,8},{3,4,6,8,10},{3,4,6,8,9},{3,4,6,8,9,10},{3,4,6,7},{3,4,6,7,10},{3,4,6,7,9},{3,4,6,7,9,10},{3,4,6,7,8},{3,4,6,7,8,10},{3,4,6,7,8,9},{3,4,6,7,8,9,10},{3,4,5},{3,4,5,10},{3,4,5,9},{3,4,5,9,10},{3,4,5,8},{3,4,5,8,10},{3,4,5,8,9},{3,4,5,8,9,10},{3,4,5,7},{3,4,5,7,10},{3,4,5,7,9},{3,4,5,7,9,10},{3,4,5,7,8},{3,4,5,7,8,10},{3,4,5,7,8,9},{3,4,5,7,8,9,10},{3,4,5,6},{3,4,5,6,10},{3,4,5,6,9},{3,4,5,6,9,10},{3,4,5,6,8},{3,4,5,6,8,10},{3,4,5,6,8,9},{3,4,5,6,8,9,10},{3,4,5,6,7},{3,4,5,6,7,10},{3,4,5,6,7,9},{3,4,5,6,7,9,10},{3,4,5,6,7,8},{3,4,5,6,7,8,10},{3,4,5,6,7,8,9},{3,4,5,6,7,8,9,10},{4},{4,10},{4,9},{4,9,10},{4,8},{4,8,10},{4,8,9},{4,8,9,10},{4,7},{4,7,10},{4,7,9},{4,7,9,10},{4,7,8},{4,7,8,10},{4,7,8,9},{4,7,8,9,10},{4,6},{4,6,10},{4,6,9},{4,6,9,10},{4,6,8},{4,6,8,10},{4,6,8,9},{4,6,8,9,10},{4,6,7},{4,6,7,10},{4,6,7,9},{4,6,7,9,10},{4,6,7,8},{4,6,7,8,10},{4,6,7,8,9},{4,6,7,8,9,10},{4,5},{4,5,10},{4,5,9},{4,5,9,10},{4,5,8},{4,5,8,10},{4,5,8,9},{4,5,8,9,10},{4,5,7},{4,5,7,10},{4,5,7,9},{4,5,7,9,10},{4,5,7,8},{4,5,7,8,10},{4,5,7,8,9},{4,5,7,8,9,10},{4,5,6},{4,5,6,10},{4,5,6,9},{4,5,6,9,10},{4,5,6,8},{4,5,6,8,10},{4,5,6,8,9},{4,5,6,8,9,10},{4,5,6,7},{4,5,6,7,10},{4,5,6,7,9},{4,5,6,7,9,10},{4,5,6,7,8},{4,5,6,7,8,10},{4,5,6,7,8,9},{4,5,6,7,8,9,10},{5},{5,10},{5,9},{5,9,10},{5,8},{5,8,10},{5,8,9},{5,8,9,10},{5,7},{5,7,10},{5,7,9},{5,7,9,10},{5,7,8},{5,7,8,10},{5,7,8,9},{5,7,8,9,10},{5,6},{5,6,10},{5,6,9},{5,6,9,10},{5,6,8},{5,6,8,10},{5,6,8,9},{5,6,8,9,10},{5,6,7},{5,6,7,10},{5,6,7,9},{5,6,7,9,10},{5,6,7,8},{5,6,7,8,10},{5,6,7,8,9},{5,6,7,8,9,10},{6},{6,10},{6,9},{6,9,10},{6,8},{6,8,10},{6,8,9},{6,8,9,10},{6,7},{6,7,10},{6,7,9},{6,7,9,10},{6,7,8},{6,7,8,10},{6,7,8,9},{6,7,8,9,10},{7},{7,10},{7,9},{7,9,10},{7,8},{7,8,10},{7,8,9},{7,8,9,10},{8},{8,10},{8,9},{8,9,10},{9},{9,10},{10}