【Java】正の有理数をすべて生成するアルゴリズムの解説と実装例

有理数とは？

有理数（Rational Number）とは、p/q という形式で表すことができる数のことです。ただし、p と q はどちらも整数であり、q は 0 以外でなければならないという条件があります。

正の有理数とは、その値が正になる数を指します。これは、p と q が両方とも正であるか、両方とも負である場合に成り立ちます。

問題の概要

本記事の課題は、与えられた数 n までの正の有理数をすべて生成することです。つまり、1 から n の間に存在する有限個の正の有理数を列挙します。そのために、1 ≤ p ≤ n かつ 1 ≤ q ≤ n を満たす分子 p・分母 q の組み合わせを順番に生成していきます。

まずは具体例で概念を確認してみましょう。

入力 : 3
出力 : 1, 1/2, 1/3, 2, 2/3, 3/2, 3

説明： この例では、p と q の両方について 1 から 3 までの値を対象とし、それらの組み合わせからなる有理数をすべて求めています。

アルゴリズムの基本的な考え方

このアルゴリズムでは、必要な組み合わせを効率よく生成するために、値の対応付け（マッピング）の考え方を利用します。ある集合の各値を別の集合の各値と対応付けることで、n × n 通りのペアをすべて作り出せます。ここでは、正の値からなる 2 つの集合を用意し、それぞれの値を対応させることで解となるペアを生成します。

n = 3 の場合、すべてのペアは次のようになります。

(1,1) , (1,2) , (1,3)
(2,1) , (2,2) , (2,3)
(3,1) , (3,2) , (3,3)

逆L字型トラバーサルによる並べ替え

これらのペアを「逆L字型（inverted L shape）」の順序でたどるように並べ替えると、次のようになります。

(1,1)
(1,2) , (2,2) , (2,1)
(1,3) , (2,3) , (3,3) , (3,2) , (3,1)

カンマをスラッシュ（/）に置き換えてみると、まさに私たちが生成したい有理数の並びになっていることが分かります。

1/1
1/2 , 2/2 , 2/1
1/3 , 2/3 , 3/3 , 3/2 , 3/1

GCD（最大公約数）による重複の除去

しかし、上記のリストには 1/1、2/2、3/3 のように、すべて同じ値（いずれも 1）を表す重複が含まれています。そこで、最大公約数（GCD）を活用してこれらの重複を取り除きます。分子と分母の最大公約数が 1 になる（互いに素な）分数だけを結果に追加することで、既約分数のみを効率的に列挙できます。

Javaでの実装例

以下が実際のJavaコードです。内部クラス PositiveRationalNumber で分数を表現し、gcd() メソッドで互いに素かどうかを判定しながら、generate() メソッドが有理数のリストを構築します。

import java.util.ArrayList;
import java.util.List;

class PositiveRational {
    private static class PositiveRationalNumber {
        private int numerator;
        private int denominator;

        public PositiveRationalNumber(int numerator, int denominator) {
            this.numerator = numerator;
            this.denominator = denominator;
        }

        @Override
        public String toString() {
            if (denominator == 1) {
                return Integer.toString(numerator);
            } else {
                return Integer.toString(numerator) + '/' + Integer.toString(denominator);
            }
        }
    }

    private static int gcd(int num1, int num2) {
        int n1 = num1;
        int n2 = num2;
        while (n1 != n2) {
            if (n1 > n2)
                n1 -= n2;
            else
                n2 -= n1;
        }
        return n1;
    }

    private static List<PositiveRationalNumber> generate(int n) {
        List<PositiveRationalNumber> list = new ArrayList<>();
        if (n > 1) {
            PositiveRationalNumber rational = new PositiveRationalNumber(1, 1);
            list.add(rational);
        }
        for (int loop = 1; loop <= n; loop++) {
            int jump = (loop % 2 == 0) ? 2 : 1;
            for (int row = 1; row <= loop - 1; row += jump) {
                if (gcd(row, loop) == 1) {
                    list.add(new PositiveRationalNumber(row, loop));
                }
            }
            for (int col = loop - 1; col >= 1; col -= jump) {
                if (gcd(col, loop) == 1) {
                    list.add(new PositiveRationalNumber(loop, col));
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        List<PositiveRationalNumber> rationals = generate(5);
        System.out.println(rationals.stream()
                .map(PositiveRationalNumber::toString)
                .reduce((x, y) -> x + ", " + y)
                .get());
    }
}

実行結果

1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 3/4, 4/3, 4, 1/5, 2/5, 3/5, 4/5, 5/4, 5/3, 5/2, 5

このように、逆L字型の走査順序とGCDによる重複チェックを組み合わせることで、1〜n の範囲に存在する正の有理数を重複なく効率的に生成することができます。