# ガウスの消去法 Gaussian Elimination
# 引数 方程式 (\@Equations)
# 戻り値 ガウスの消去法 (@GaussianElimination)
sub GAUSSIANELIMINATION{
	my ($Equations) = @_;
	my @GaussianElimination = ();
	my @SortEquations = @$Equations;
	my @TempEquations = ();
	my $Column = $#$Equations;
	my $Row = $#{$$Equations[0]};
	
	# 配列数の確認
	for(my $i = 1; $i <= $Column; $i++){
		if($Row != $#{$$Equations[$i]}){
			return 0;
		}
	}
	if($Column != ($Row - 1)){
		return 0;
	}
	
	# 上三角行列 前進消去
	for(my $i = 0; $i <= $Column; $i++){
		# 縦列を[最高値, 0以上, 0] にソートする
		@SortEquations = &MatrixColumnSort($i, $i, \@SortEquations);
		# 縦列$i番目 $SortEquations[$i]をコピー
		$TempEquations[$i] = $SortEquations[$i];
	
		# $jの$RowNumber番目の要素を0にする
		my $RowNumber = $i;
		for(my $j = ($RowNumber + 1); $j <= $Column; $j++){
			last if($SortEquations[$j][$RowNumber] == 0);
	
			my $PriceI = $SortEquations[$i][$RowNumber];
			my $PriceJ = $SortEquations[$j][$RowNumber];
			for(my $k = $RowNumber; $k <= $Row; $k++){
				my $Diff = ($SortEquations[$j][$k] * $PriceI) - ($SortEquations[$i][$k] * $PriceJ);
	
				$SortEquations[$j][$k] = $Diff;
			}
		}
	}
	
	# 後退代入
	$GaussianElimination[$Row - 1] = $TempEquations[$Column][$Row] / $TempEquations[$Column][$Row - 1];
	for(my $i = $Column - 1; $i >= 0; $i--){
		my $tmp = $TempEquations[$i][$Row];
	
		for(my $j = $Row - 1; $j > $i; $j--){
			$tmp = $tmp - ($TempEquations[$i][$j] * $GaussianElimination[$j]);
		}
	
		# ガウスの消去法 Gaussian Elimination
		$GaussianElimination[$i] = $tmp / $TempEquations[$i][$i];
	}
	
	return @GaussianElimination;
}
	
# 縦列を[最高値, 0以上, 0] にソートする
# 引数 縦列位置 行列 ($ColumnNumber, $RowNumber, \@SortEquations)
# 戻り値 MatrixColumnSort (@Matrix);
sub MatrixColumnSort{
	my ($ColumnNumber, $RowNumber, $SortEquations) = @_;
	my @Matrix = @$SortEquations;
	my @TempMatrix = ();
	my $Count = $#$SortEquations;
	my $Highest = 0;
	
	# [0] 最高値 [1] 0以上 [2] 0
	$TempMatrix[0][0] = $$SortEquations[$ColumnNumber];
	for(my $i = $ColumnNumber + 1; $i <= $Count; $i++){
		my $Price = $$SortEquations[$i][$RowNumber];
	
		if($Price == 0){
			$TempMatrix[2][$#{$TempMatrix[2]} + 1] = $$SortEquations[$i];
		}else {
			if($Highest < $Price){
				$TempMatrix[1][$#{$TempMatrix[1]} + 1] = $TempMatrix[0][0];
				$TempMatrix[0][0] = $$SortEquations[$i];
				# 最高値
				$Highest = $Price;
			}else {
				$TempMatrix[1][$#{$TempMatrix[1]} + 1] = $$SortEquations[$i];
			}
		}
	}
	
	# 配列の入れ替え
	my $Num = $ColumnNumber;
	for(my $i = 0; $i <= 2; $i++){
		for(my $j = 0; $j <= $#{$TempMatrix[$i]}; $j++){
			$Matrix[$Num] = $TempMatrix[$i][$j];
			$Num++;
		}
	}
	
	return @Matrix;
}