N個の要素を２つずつのペア，ローテーションする効率的な方法

Question

N個の要素(1,2,・・・,N)があり(Nは68や120ぐらいの大きさの数字を想定しています)，それらを重複がないように2個ずつのペアに分けたいです(例えば(1,2),(3,4),・・・,(N-1,N)のようにN/2個のペアを作りたい)．

この作業を何回も繰り返したいのですが，できるかぎり違う組み合わせでペアを組みたいです．

そして入力として要素の番号と何回目の作業かを表す数字を与えたらペア相手の要素番号が返ってくるようなできるだけ計算量の小さい数式を作りたいのですが何か効率的な方法はないでしょうか．

おそらくN個の要素を2グループに分けたら簡単にローテーションできると思うのですが，それだとすべての組み合わせパターンは網羅できないかと思います．
全ての組み合わせパターンを網羅できるような方法はありますか?(またはそれに近い数の組み合わせ)

Comments

[jimbe]

斜めにも置ける [N-クイーン]( https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3 )というところでしょうか.
...とも思ったのですが, 同じ値は使えないですし, 違いますね.

[fana]

> 要素の番号と何回目の作業かを表す数字を与えたらペア相手の要素番号が返ってくるようなできるだけ計算量の小さい数式

これの意味するところは，【実際に(再帰とか何とかで)頑張って指定回目までのパターンを計算せずとも，特定の要素番号のペア相手だけならばどうにかしてわかるだろう】的な話なのかな．

例えば，データが4個{0,1,2,3}のときのパターンは
(0,1)(2,3)
(0,2)(1,3)
(0,3)(1,2)
の３パターンしかないが，このパターンの並べ方の上では
「要素0番」の「k回目」の相手を求める式は f(0,k)=k と書ける．
そんな感じで全パターンを「ある並べ方」に並べた状態を前提とするならば，
「要素i番」の「k回目」の相手を算出する「式」を f(i,k)=??? という形で書けないか？　という話か．
（全パターンを愚直に再帰で求める手順には法則性があるのだから，f(i,k)=??? という式で表すことは可能そうに思うが…）

Answer 1

こんにちは。
以下ではペアの順序は無視して考えています。
例：(1,3)(2,4) = (1,3)(4,2) = (2,4)(1,3)

全て網羅するためのアルゴリズムですが、私が思いついたのは単純に再帰で求める方法でした。
順序を無視するのでペアになる片方一つを固定して、その残りの数値を分岐させ、二つずつ再帰でネストして求めるという方針です。

#include <stdio.h>
#define N 6

void search(int *);
int Index(int *,int ,int );
void show(int *);
void show_array(int *);

//グローバル変数
int stock[N+1];
int n,k,count;


int main(void){
	int i;
	// array = [0,0,0,...,0,-1]
	int array[N+1]={0};
	array[N] = -1;
	// stock = [1,1,1,...,1,-1]
	for(i=0;i<N;i++){stock[i] = 1;}
	stock[N] = -1;
	// グローバル変数の初期化
	count = 0;
	n = k = 0;
	
	//入力
	printf("繰返し回数->");
	scanf("%d",&k);
	printf("要素の番号->");
	scanf("%d",&n);

	//探索
	search(array);
	return 0;
}

//再帰関数
void search(int *array){
	int i;
	int index_array0 = Index(array,0,0);
	int index_stock1 = Index(stock,1,0);
	
	if(count >= k){
		return ;
	}
	//探索中
	if(index_array0 != -1){
		//一つ目を配置
		array[index_array0] = index_stock1 + 1;
		stock[index_stock1] = 0;
		
		//二つ目を配置
		//stockの1の数だけ分岐
		i = Index(stock,1,0);
		do{
			array[index_array0 +1]=i+1;
			stock[i] = 0;
			
			//再探索
			search(array);
			
			//戻す一つ
			stock[i] = 1;
			array[index_array0 +1] = 0;
			
		}while((i=Index(stock,1,i+1)) != -1);
		//もう一つ戻す
		stock[index_stock1] = 1;
		array[index_array0] = 0;
	//解
	}else{
		//表示
		count++;
		if(count == k){
			show_array(array);
			show(array);
		}
	}
}



/* 添え字を返す関数 */
// 第一引数 : 配列の先頭アドレス
// 第二引数 : 検索対象の数値
// 第三引数 : 検索開始インデックス
int Index(int *p,int a,int i){
	int *q = p;
	int c = 0;
	while( (*(q+i) != -1) && (*(q+i)!=a)){
		c++;
		q++;
	}
	
	if(*(q+i) == -1){
		return -1;
	}else{
		return i+c;
	}
}



// 入力されたペアを表示
void show(int *p){
	int i;
	for(i=0;i<N;i+=2){
		if( *(p+i)==n){
			printf("%dのペアは%d\n",n,*(p+i+1));
		}
		if( *(p+i+1)==n ){
			printf("%dのペアは%d\n",n,*(p+i));
		}
	}
}


// 配列の全てを表示
void show_array(int *p){
	int i;
	for(i=0;i<N;i+=2){
		printf("(%d %d) " ,*(p+i),*(p+i+1));}
	printf("\n");
}

ところでN=4のときであれば

1. (1,2)(3,4)
2. (1,3)(2,4)
3. (1,4)(2,3)

とペアの組は三種類あり、N=6のときであれば15種類あります。
このペアというのは、辺のない正N角形で各頂点から1本ずつ線を引いている図形と対応できるので
(N-1)!! = (N-1)(N-3)(N-5)...*1 個あります。(二重階乗)
このように階乗で増えていくのでN=14くらいから再帰が深くなりすぎて最後までは辿りつかないようです。

ここより先追記。
二重階乗であることを使えば再帰しなくても済んだので効率的に求めることができました。
N=200で1億回目でも簡単に求まります。
自分が試したところN=10000000程度でも問題はなかったです。

#include <stdio.h>
#define N  200

void show(int *,int ,int );

int main(void){
	int i,k,n,index,count=0;
	// S = {0,0,0,...,0,-1}
	int S[N/2] = {0};
	S[N/2-1] = -1;
	
	//入力
	printf("繰返し回数->");
	scanf("%d",&k);
	printf("要素の番号->");
	scanf("%d",&n);
	//昇順列の二つずつ各ペアに置換の求める
	while(count<k-1){
		index = 0;
		count++;
		//毎回表示するならこれを実行
		//show(S,count,n);
		
		S[index]++ ;
		// 繰り上がり
		while(S[index] >= N-1-2*index){
			S[index] = 0;
			S[index+1]++;
			index++;
		}
		//全部調べたら終了
		//配列最後の-1は表示時の終了条件で使うので代入
		if(S[N/2-1] != -1){
			S[N/2-1] = -1;
			break;
		}
	}
	
	//表示
	show(S,k,n);
	return 0;
}

void show(int *S,int k,int n){
	int i,temp,index=0;
	// A[] = {1,2,3,4,...,N}
	int A[N];
	for(i=0;i<N;i++){A[i] = i+1;}
	while(*S != -1){
		/* Sの置換表現通りに入れ替え */
		temp = A[2*index+1];
		A[2*index+1] = A[ 2*index+1+(*S)];
		A[2*index+1+(*S)] = temp;
		//次の置換へ
		index++;
		S++;
	}
	
	printf("\n%d回目: ",k);
	for(i=0;i<N;i+=2){printf("(%d,%d) ",A[i],A[i+1]);}
	for(i=0;i<N;i+=2){
		if( A[i]==n ){printf("\n%dのペアは%dです。\n",n,A[i+1]);break;}
		if(A[i+1]==n){printf("\n%dのペアは%dです。\n",n, A[i] );break;}
		if(i==N-2){printf("%dのペアはありません\n",n);}
	}
	
}

少し数学チックに解いた部分はあるのですが、アルゴリズム的にはN=6の場合
(12)(34)(56)の一つ目の(12)の部分をみて左の数値を固定して、右の数値を自分より後の数値と入れ替えることを考えます。（”後”とは入れ替えないような自分自身と入れ替える場合も含みます）
(1[2])(34)(56)だから2の移動先は2,3,4,5,6の5通りで入れ替えた後はそれより右の組だけを考えます。たとえばこの例で2が5と入れ替わったとしましょう。すると
(15)(34)(26)となり、ここで(15)は固定して残りの(34)(26)で同じことを繰り返すことによって同じパターンが出ずに全てを網羅できます。
ここで入れ替えた所をそれぞれ自分自身からの距離(2と5を入れ替えるのであれば3)を配列にして格納することで再帰することなく、求めることができます。
ちなみN=6の場合だと2の移動先が5通り、その次の右側の数字の移動先が3通り、その次の右側の数字が1通りなので全部で15通りと、ちゃんとN!!通りになっていることが確かめられます。

Answer 2

そして入力として要素の番号と何回目の作業かを表す数字を与えたらペア相手の要素番号が返ってくるようなできるだけ計算量の小さい数式を作りたいのですが何か効率的な方法はないでしょうか．

すみません。これの意味がよく分かりません。

全ての組み合わせパターンを網羅できるような方法はありますか?

書いてみました。

#include <stdio.h>

#define N 20

int n, a[N];

void generate(int i)
{
	if (i == n) {
		for (i = 0; i < n; i += 2) printf(" (%d,%d)", a[i], a[i + 1]);
		putchar('\n');
	}
	else {
		for (int j = i + 1; j < n; j++) {
			int t = a[j];
			for (int k = j - 1; k > i; k--) a[k + 1] = a[k];
			a[i + 1] = t;
			generate(i + 2);
			for (int k = i + 1; k < j; k++) a[k] = a[k + 1];
			a[j] = t;
		}
	}
}

int main(void)
{
	while (printf("n: "), scanf("%d", &n) == 1 && n < N && n % 2 == 0) {
		for (int i = 0; i < n; i++) a[i] = i + 1; 
		generate(0);
	}
}

n が大きい時は、表示に時間がかかるので、次のようにファイルに出力しましょう。
$ echo 14 | ./a.out > result.txt

追記
意味が分かりました。

#include <stdio.h>

#define N  68

int k;    // 繰返し回数(kaisu)
int n;    // 要素の番号(number)
int c;    // 生成個数(count)
int a[N]; // 要素の列(array)

void generate(int i)
{
	if (c == k) return;
    if (i == N) {
		if (++c == k) {
			int p;  // ペアの相手
			for (i = 0; i < N; i += 2) {
				printf(" (%d,%d)", a[i], a[i + 1]);
				if (a[i + 1] == n) p = a[i];
				else if (a[i] == n) p = a[ i + 1];
			}
			printf("\n %d の相手は %d\n\n", n, p);
		}
    }
    else {
        for (int j = i + 1; j < N; j++) {
            int t = a[j];
            for (int k = j - 1; k > i; k--) a[k + 1] = a[k];
            a[i + 1] = t;
            generate(i + 2);
            for (int k = i + 1; k < j; k++) a[k] = a[k + 1];
            a[j] = t;
        }
    }
}

int main(void)
{
	while (1) {
		printf("繰返し回数: ");
		if (scanf("%d", &k) != 1) return 1;
		printf("要素の番号: ");
		if (scanf("%d", &n) != 1 || n < 1 || n > N) return 2;
		for (int i = 0; i < N; i++) a[i] = i + 1;
		c = 0;
		generate(0);
	}
}

追記2
上記のコードにはバグがありました。調査します。

追記3
j < n を j < N に修正しました。

追記4
関数 generate の中の if (c == k) return; は、ここではなく、
再帰呼出しの generate(i + 2); の直後に置いたほうが、効率が良くなります。

Answer 3

2個ずつのペアに分けるだけなら，
N個の要素を適当に並び替えて，先頭から２個ずつ取り出せばよい．

• 全パターン網羅することに拘らないならば，上記の「適当に並び替えて」の部分は例えば「ランダムに並べ替える処理」とかで．（乱数のSEEDを固定すれば，作業回数に対する再現性も持たせることも可能）

• 全パターンを網羅することが必須なら，

上記の「適当に並び替えて」の部分を「N個の要素を一列に並べる全ての並べ方を列挙する手段(C++ならstd::next_permutationとかが使える)」を用いるような形態とすればよいのでは．