# 組合せ生成 Combination Generator
# 引数 n個 r個 値 ($n, $r, \@Value)
# 戻り値 組合せ生成 (@Combination)
sub COMBINATIONGENERATOR{
	my ($n, $r, $Value) = @_;
	my @Combination = ();
	my @BetweenValue = ();
	my @BetweenValuePos = ();
	my $N = int($n);
	my $R = int($r);
	my $Start = 0;
	my $Position = 0;
	my $DiffR2 = ($R - 2) - 1;
	my $Limit = ($N - $R) + 1;
	
	# 個数と配列数の確認
	if(($N <= 0) || ($R <= 0) || ($N < $R) || ($N > @Value)){
		return 0;
	}
	
	if($R == 1){
		# 組合せ生成 Combination Generator
		@Combination = @Value;
	}elsif($R == 2){
		for(my $i = 0; $i < ($N - 1); $i++){
			for(my $j = $i + 1; $j < $N; $j++){
				# 組合せ生成 Combination Generator
				$Combination[$Position] = join " ", ($$Value[$i], $$Value[$j]);
				# 配列の位置
				$Position++;
			}
		}
	}else {
		for(my $i = 0; $i < $Limit; $i++){
			# 組合せで使用する値の開始位置
			$Start = 0;	
			# 両端を除く組合せで使用する配列の初期位置
			for(my $j = 0; $j <= $DiffR2; $j++){
				$BetweenValuePos[$j] = $i + ($j + 1);
			}
	
			# 右端から一列を選ぶまで
			while($BetweenValuePos[0] <= $Limit){
				# 組合せで使用する値
				for(my $j = $Start; $j <= $DiffR2; $j++){
					$BetweenValue[$j] = $$Value[$BetweenValuePos[$j]];
				}		
	
				# 右端まで選ぶ
				for(my $j = $BetweenValuePos[$DiffR2] + 1; $j < $N; $j++){
					# 組合せ生成 Combination Generator
					$Combination[$Position] = join " ", ($$Value[$i], @BetweenValue, $$Value[$j]);
					# 配列の位置
					$Position++;
				}
	
				# 組合せで使用する配列の位置を更新
				for(my $j = $DiffR2; $j >= 0; $j--){
					# 次に組合せで使用する値の開始位置
					$Start = $j;
					# 配列の位置と値
					$BetweenValuePos[$j] = $BetweenValuePos[$j] + 1;
					$BetweenValue[$j] = $$Value[$BetweenValuePos[$j]];	
	
					if($j == $DiffR2){
						# 右端と接していないなら
						last if($BetweenValuePos[$j] != ($N - 1));
					}elsif($BetweenValuePos[$j] != ($BetweenValuePos[$j + 1] - 1)){
						# 右隣と接していないなら
						for(my $k = $j + 1; $k <= $DiffR2; $k++){
							$BetweenValuePos[$k] = $BetweenValuePos[$k - 1] + 1;
							$BetweenValue[$k] = $$Value[$BetweenValuePos[$k]];
						}
	
						last;
					}
				}
			}
		}
	}
	
	return @Combination;
}