有限自然数列のナンバリング案2
前回に続いて有限自然数列のナンバリングについて考えます。
今回は、第二の案です。
定式化第二案
・数列 $${\{1\}}$$ の番号を $${1}$$ とする。
・番号 $${k}$$ が与えられてある数列に対し、最終項が、 $${1}$$ 大きいだけの違いを持つ数列があった場合、その数列 の番号を、$${2k}$$ とする。
・番号 $${k}$$ が与えられてある数列に対し、新しい項として、 $${1}$$ を付け加えただけの数列があった場合、その数列 の番号を、$${2k+1}$$ とする。
第一案は、既存の数列(番号を$${k}$$とする)に対し、新項として$${1}$$が追加された数列の番号を$${2k}$$、最終項が$${1}$$大きくなった数列の番号を$${2k+1}$$としていましたが、ご覧のように第二案は逆になっています。
具体例
$${ 1 = \{1\}, \hspace{50pt} 13 = \{1,2,1\}, \hspace{36pt} 25 = \{1,3,1\},}$$
$${ 2 = \{2\}, \hspace{50pt} 14 = \{1,1,2\} ,\hspace{38pt} 26 = \{1,2,2\},}$$
$${ 3 = \{1,1\}, \hspace{40pt} 15 = \{1,1,1,1\} ,\hspace{30pt} 27 = \{1,2,1,1\},}$$
$${ 4 = \{3\}, \hspace{50pt} 16 = \{5\} ,\hspace{56pt} 28 = \{1,1,3\},}$$
$${ 5 = \{2,1\}, \hspace{40pt} 17 = \{4,1\} ,\hspace{48pt} 29 = \{1,1,2,1\},}$$
$${ 6 = \{1,2\}, \hspace{40pt} 18 = \{3,2\} ,\hspace{48pt} 30 = \{1,1,1,2\},}$$
$${ 7 = \{1,1,1\}, \hspace{30pt} 19 = \{3,1,1\} ,\hspace{38pt} 31 = \{1,1,1,1,1\},}$$
$${ 8 = \{4\}, \hspace{50pt} 20 = \{2,3\} ,\hspace{46pt} 32 = \{6\},}$$
$${ 9 = \{3,1\}, \hspace{40pt} 21 = \{2,2,1\} ,\hspace{38pt} 33 = \{5,1\},}$$
$${10 = \{2,2\}, \hspace{36pt} 22 = \{2,1,2\} ,\hspace{37pt} 34 = \{4,2\},}$$
$${11 = \{2,1,1\}, \hspace{26pt} 23 = \{2,1,1,1\} ,\hspace{29pt} 35 = \{4,1,1\},}$$
$${12 = \{1,3\} ,\hspace{36pt} 24 = \{1,4\} ,\hspace{46pt} 36 = \{3,3\},…}$$
数列→番号 変換方法
数列から番号へ変換する方法を説明します。第一案に比べてかなり簡明です。
数列の項、$${1,2,3,4,5,...}$$を、$${1,10,100,1000,10000,...}$$に置き換え、コンマを取り除き、二進数と見なして数値に直す。これだけです。
番号→数列 変換方法
こちらも簡単です。
番号を二進数に変換します。$${ｋ}$$桁になったとします。
右端に目印になる$${1}$$を付加します。以下、$${1}$$と$${0}$$からなる$${k+1}$$個の数字の並びを文字列と呼びます。
文字列を左から見ていって、
$${11...}$$→ 数列に$${1}$$を追加し、文字列から一番左の$${1}$$を削除。
$${101...}$$→ 数列に$${2}$$を追加し、文字列左側にある$${10}$$を削除。
$${1001...}$$→ 数列に$${3}$$を追加し、同様に$${100}$$を削除。
$${10001...}$$→ 数列に$${4}$$を追加し、同様に$${1000}$$を削除。
．．．
$${10000…001... {\scriptsize(k-1個の0が1に挟まれている状態)}}$$→数列に$${k}$$を追加し、$${1000…00}$$を削除。
以下同様
これを文字列が一文字（最初に付加した後方の$${1}$$）になるまで繰り返す。
これで、番号から数列への変換ができます。
以下、番号から数列へ、数列から番号へ変換するCのプログラムを添えておきます。
#include<stdio.h>
#include<stdlib.h>
void f2(int n){
char r[32];
int i,flag,m=(n<<1)|1;
for(flag=0,i=31;i>=0;i--)if(m & (1<<i))r[flag++]=i;
r[flag]=-1;
printf("{%d",r[0]-r[1]);
for(i=1;r[i+1]!=-1;i++)printf(",%d",r[i]-r[i+1]);
printf("}");
}
int g2(char *b){
int i=0,j,r=1<<(b[0]-1);
while((j=b[++i])>0)r=(r<<j)|(1<<(j-1));
return r;
}
int main(int argc,char *argv[]){
int i,x,lx=0;
char b[6]={0,0,0,0,0,0},c[][3]={"",",1",",2",",3",",4",",5",",6",",7",",8",",9"};
for(i=1;i<101;i++)printf("\n%4d = ",i),f2(i);
printf("\n\n");
for(b[0]=1;b[0]<5;b[0]++) for(b[1]=0;b[1]<4;b[1]++)
for(b[2]=0;b[2]<3;b[2]++) for(b[3]=0;b[3]<3;b[3]++)
for(b[4]=0;b[4]<3;b[4]++){
x=g2(b);
if(x!=lx)printf("\n%4d = {%d%s%s%s%s}",x,b[0],c[b[1]],c[b[2]],c[b[3]],c[b[4]]);
lx=x;
}
printf("\nend\n");
return 0;
}
以下、上記プログラムの出力結果です。
1 = {1}
2 = {2}
3 = {1,1}
4 = {3}
5 = {2,1}
6 = {1,2}
7 = {1,1,1}
8 = {4}
9 = {3,1}
10 = {2,2}
11 = {2,1,1}
12 = {1,3}
13 = {1,2,1}
14 = {1,1,2}
15 = {1,1,1,1}
16 = {5}
17 = {4,1}
18 = {3,2}
19 = {3,1,1}
20 = {2,3}
21 = {2,2,1}
22 = {2,1,2}
23 = {2,1,1,1}
24 = {1,4}
25 = {1,3,1}
26 = {1,2,2}
27 = {1,2,1,1}
28 = {1,1,3}
29 = {1,1,2,1}
30 = {1,1,1,2}
31 = {1,1,1,1,1}
32 = {6}
33 = {5,1}
34 = {4,2}
35 = {4,1,1}
36 = {3,3}
37 = {3,2,1}
38 = {3,1,2}
39 = {3,1,1,1}
40 = {2,4}
41 = {2,3,1}
42 = {2,2,2}
43 = {2,2,1,1}
44 = {2,1,3}
45 = {2,1,2,1}
46 = {2,1,1,2}
47 = {2,1,1,1,1}
48 = {1,5}
49 = {1,4,1}
50 = {1,3,2}
51 = {1,3,1,1}
52 = {1,2,3}
53 = {1,2,2,1}
54 = {1,2,1,2}
55 = {1,2,1,1,1}
56 = {1,1,4}
57 = {1,1,3,1}
58 = {1,1,2,2}
59 = {1,1,2,1,1}
60 = {1,1,1,3}
61 = {1,1,1,2,1}
62 = {1,1,1,1,2}
63 = {1,1,1,1,1,1}
64 = {7}
65 = {6,1}
66 = {5,2}
67 = {5,1,1}
68 = {4,3}
69 = {4,2,1}
70 = {4,1,2}
71 = {4,1,1,1}
72 = {3,4}
73 = {3,3,1}
74 = {3,2,2}
75 = {3,2,1,1}
76 = {3,1,3}
77 = {3,1,2,1}
78 = {3,1,1,2}
79 = {3,1,1,1,1}
80 = {2,5}
81 = {2,4,1}
82 = {2,3,2}
83 = {2,3,1,1}
84 = {2,2,3}
85 = {2,2,2,1}
86 = {2,2,1,2}
87 = {2,2,1,1,1}
88 = {2,1,4}
89 = {2,1,3,1}
90 = {2,1,2,2}
91 = {2,1,2,1,1}
92 = {2,1,1,3}
93 = {2,1,1,2,1}
94 = {2,1,1,1,2}
95 = {2,1,1,1,1,1}
96 = {1,6}
97 = {1,5,1}
98 = {1,4,2}
99 = {1,4,1,1}
100 = {1,3,3}
1 = {1}
3 = {1,1}
7 = {1,1,1}
15 = {1,1,1,1}
31 = {1,1,1,1,1}
62 = {1,1,1,1,2}
30 = {1,1,1,2}
61 = {1,1,1,2,1}
122 = {1,1,1,2,2}
14 = {1,1,2}
29 = {1,1,2,1}
59 = {1,1,2,1,1}
118 = {1,1,2,1,2}
58 = {1,1,2,2}
117 = {1,1,2,2,1}
234 = {1,1,2,2,2}
6 = {1,2}
13 = {1,2,1}
27 = {1,2,1,1}
55 = {1,2,1,1,1}
110 = {1,2,1,1,2}
54 = {1,2,1,2}
109 = {1,2,1,2,1}
218 = {1,2,1,2,2}
26 = {1,2,2}
53 = {1,2,2,1}
107 = {1,2,2,1,1}
214 = {1,2,2,1,2}
106 = {1,2,2,2}
213 = {1,2,2,2,1}
426 = {1,2,2,2,2}
12 = {1,3}
25 = {1,3,1}
51 = {1,3,1,1}
103 = {1,3,1,1,1}
206 = {1,3,1,1,2}
102 = {1,3,1,2}
205 = {1,3,1,2,1}
410 = {1,3,1,2,2}
50 = {1,3,2}
101 = {1,3,2,1}
203 = {1,3,2,1,1}
406 = {1,3,2,1,2}
202 = {1,3,2,2}
405 = {1,3,2,2,1}
810 = {1,3,2,2,2}
2 = {2}
5 = {2,1}
11 = {2,1,1}
23 = {2,1,1,1}
47 = {2,1,1,1,1}
94 = {2,1,1,1,2}
46 = {2,1,1,2}
93 = {2,1,1,2,1}
186 = {2,1,1,2,2}
22 = {2,1,2}
45 = {2,1,2,1}
91 = {2,1,2,1,1}
182 = {2,1,2,1,2}
90 = {2,1,2,2}
181 = {2,1,2,2,1}
362 = {2,1,2,2,2}
10 = {2,2}
21 = {2,2,1}
43 = {2,2,1,1}
87 = {2,2,1,1,1}
174 = {2,2,1,1,2}
86 = {2,2,1,2}
173 = {2,2,1,2,1}
346 = {2,2,1,2,2}
42 = {2,2,2}
85 = {2,2,2,1}
171 = {2,2,2,1,1}
342 = {2,2,2,1,2}
170 = {2,2,2,2}
341 = {2,2,2,2,1}
682 = {2,2,2,2,2}
20 = {2,3}
41 = {2,3,1}
83 = {2,3,1,1}
167 = {2,3,1,1,1}
334 = {2,3,1,1,2}
166 = {2,3,1,2}
333 = {2,3,1,2,1}
666 = {2,3,1,2,2}
82 = {2,3,2}
165 = {2,3,2,1}
331 = {2,3,2,1,1}
662 = {2,3,2,1,2}
330 = {2,3,2,2}
661 = {2,3,2,2,1}
1322 = {2,3,2,2,2}
4 = {3}
9 = {3,1}
19 = {3,1,1}
39 = {3,1,1,1}
79 = {3,1,1,1,1}
158 = {3,1,1,1,2}
78 = {3,1,1,2}
157 = {3,1,1,2,1}
314 = {3,1,1,2,2}
38 = {3,1,2}
77 = {3,1,2,1}
155 = {3,1,2,1,1}
310 = {3,1,2,1,2}
154 = {3,1,2,2}
309 = {3,1,2,2,1}
618 = {3,1,2,2,2}
18 = {3,2}
37 = {3,2,1}
75 = {3,2,1,1}
151 = {3,2,1,1,1}
302 = {3,2,1,1,2}
150 = {3,2,1,2}
301 = {3,2,1,2,1}
602 = {3,2,1,2,2}
74 = {3,2,2}
149 = {3,2,2,1}
299 = {3,2,2,1,1}
598 = {3,2,2,1,2}
298 = {3,2,2,2}
597 = {3,2,2,2,1}
1194 = {3,2,2,2,2}
36 = {3,3}
73 = {3,3,1}
147 = {3,3,1,1}
295 = {3,3,1,1,1}
590 = {3,3,1,1,2}
294 = {3,3,1,2}
589 = {3,3,1,2,1}
1178 = {3,3,1,2,2}
146 = {3,3,2}
293 = {3,3,2,1}
587 = {3,3,2,1,1}
1174 = {3,3,2,1,2}
586 = {3,3,2,2}
1173 = {3,3,2,2,1}
2346 = {3,3,2,2,2}
8 = {4}
17 = {4,1}
35 = {4,1,1}
71 = {4,1,1,1}
143 = {4,1,1,1,1}
286 = {4,1,1,1,2}
142 = {4,1,1,2}
285 = {4,1,1,2,1}
570 = {4,1,1,2,2}
70 = {4,1,2}
141 = {4,1,2,1}
283 = {4,1,2,1,1}
566 = {4,1,2,1,2}
282 = {4,1,2,2}
565 = {4,1,2,2,1}
1130 = {4,1,2,2,2}
34 = {4,2}
69 = {4,2,1}
139 = {4,2,1,1}
279 = {4,2,1,1,1}
558 = {4,2,1,1,2}
278 = {4,2,1,2}
557 = {4,2,1,2,1}
1114 = {4,2,1,2,2}
138 = {4,2,2}
277 = {4,2,2,1}
555 = {4,2,2,1,1}
1110 = {4,2,2,1,2}
554 = {4,2,2,2}
1109 = {4,2,2,2,1}
2218 = {4,2,2,2,2}
68 = {4,3}
137 = {4,3,1}
275 = {4,3,1,1}
551 = {4,3,1,1,1}
1102 = {4,3,1,1,2}
550 = {4,3,1,2}
1101 = {4,3,1,2,1}
2202 = {4,3,1,2,2}
274 = {4,3,2}
549 = {4,3,2,1}
1099 = {4,3,2,1,1}
2198 = {4,3,2,1,2}
1098 = {4,3,2,2}
2197 = {4,3,2,2,1}
4394 = {4,3,2,2,2}
end