A rational number is of the form p/q where p and q are integers. The problem statement is to generate rational number such that any particular number is generated in a finite time. For a given n, we generate all rational numbers where 1 <= p <= n and 1 <= q <= n Examples:
Input : 5
Output : 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
Input : 7
Output :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, 1/6, 5/6, 6/5, 6, 1/7, 2/7, 3/7,
4/7, 5/7, 6/7, 7/6, 7/5, 7/4, 7/3, 7/2, 7
In mathematical terms a set is countably infinite if its elements can be mapped on a one to one basis with the set of natural numbers. The problem statement here is to generate combinations of p/q where both p and q are integers and any particular combination of p and q will be reached in a finite no. of steps. If p is incremented 1, 2, 3… etc keeping q constant or vice versa all combinations cannot be reached in finite time. The way to handle this is to imagine the natural numbers arranged as a row, col of a matrix (1, 1) (1, 2) (1, 3) (1, 4) (2, 1) (2, 2) (2, 3) (2, 4) (3, 1) (3, 2) (3, 3) (3, 4) (4, 1) (4, 2) (4, 3) (4, 4) These elements are traversed in an inverted L shape in each iteration (1, 1) (1, 2), (2, 2) (2, 1) (1, 3), (2, 3), (3, 3), (3, 2), (3, 1) yielding 1/1 1/2, 2/2, 2/1 1/3, 2/3, 3/3, 3/2, 3/1 Obviously this will yield duplicates as 2/1 and 4/2 etc, but these can be weeded out by using the Greatest common divisor constraint.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;class RationalNumber { int numerator, denominator; public: RationalNumber(int n, int d) { numerator = n; denominator = d; } string toString() { if (denominator == 1) { return to_string(numerator); } else { return to_string(numerator) + "/" + to_string(denominator); } }};vector<RationalNumber> generate(int n){ vector<RationalNumber> list ; if (n > 1) { RationalNumber rational (1, 1); list.push_back(rational); } for (int loop = 1; loop <= n; loop++) { int jump = 1; // Handle even case if (loop % 2 == 0) jump = 2; else jump = 1; for (int row = 1; row <= loop - 1; row += jump) { // Add only if there are no common divisors // other than 1 if (__gcd(row, loop) == 1) { RationalNumber rational(row, loop); list.push_back(rational); } } for (int col = loop - 1; col >= 1; col -= jump) { // Add only if there are no common divisors // other than 1 if (__gcd(col, loop) == 1) { RationalNumber rational (loop, col); list.push_back(rational); } } } return list;}// Driver Codeint main(){ vector<RationalNumber> rationals = generate(7); for (RationalNumber rational : rationals) cout << rational.toString() + ", ";}// This code is contributed by phasing17 |
Java
// Java program import java.util.ArrayList;import java.util.List; class Rational { private static class RationalNumber { private int numerator; private int denominator; public RationalNumber(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); } } } /** * Greatest common divisor * @param num1 * @param num2 * @return */ 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<RationalNumber> generate(int n) { List<RationalNumber> list = new ArrayList<>(); if (n > 1) { RationalNumber rational = new RationalNumber(1, 1); list.add(rational); } for (int loop = 1; loop <= n; loop++) { int jump = 1; // Handle even case if (loop % 2 == 0) jump = 2; else jump = 1; for (int row = 1; row <= loop - 1; row += jump) { // Add only if there are no common divisors other than 1 if (gcd(row, loop) == 1) { RationalNumber rational = new RationalNumber(row, loop); list.add(rational); } } for (int col = loop - 1; col >= 1; col -= jump) { // Add only if there are no common divisors other than 1 if (gcd(col, loop) == 1) { RationalNumber rational = new RationalNumber(loop, col); list.add(rational); } } } return list; } public static void main(String[] args) { List<RationalNumber> rationals = generate(7); System.out.println(rationals.stream(). map(RationalNumber::toString). reduce((x, y) -> x + ", " + y).get()); }} |
Python3
# Python3 program to implement the approachfrom math import gcdclass RationalNumber: def __init__(self, numerator, denominator): self.numerator = numerator; self.denominator = denominator; def __repr__(self): if (self.denominator == 1): return str(self.numerator) else: return str(self.numerator)+ '/' + str(self.denominator);def generate(n): list1 = []; if (n > 1): rational = RationalNumber(1, 1); list1.append(rational); for loop in range (1, n + 1): jump = 1; # Handle even case if (loop % 2 == 0): jump = 2; else: jump = 1; for row in range(1, loop, jump): # Add only if there are no common divisors # other than 1 if (gcd(row, loop) == 1): rational = RationalNumber(row, loop); list1.append(rational); for col in range(loop - 1, 0, -jump): # Add only if there are no common divisors # other than 1 if (gcd(col, loop) == 1): rational = RationalNumber(loop, col); list1.append(rational); return list1;# Driver Coderationals = generate(7);print(", ".join(repr(rational) for rational in rationals))# This code is contributed by phasing17 |
C#
// C# program to implement the approachusing System;using System.Linq;using System.Collections.Generic;public class RationalNumber { private int numerator; private int denominator; public RationalNumber(int numerator, int denominator) { this.numerator = numerator; this.denominator = denominator; } public string toString() { if (denominator == 1) { return Convert.ToString(numerator); } else { return Convert.ToString(numerator) + '/' + Convert.ToString(denominator); } }}class Rational { /** * Greatest common divisor * @param num1 * @param num2 * @return */ 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<RationalNumber> generate(int n) { List<RationalNumber> list = new List<RationalNumber>(); if (n > 1) { RationalNumber rational = new RationalNumber(1, 1); list.Add(rational); } for (int loop = 1; loop <= n; loop++) { int jump = 1; // Handle even case if (loop % 2 == 0) jump = 2; else jump = 1; for (int row = 1; row <= loop - 1; row += jump) { // Add only if there are no common divisors // other than 1 if (gcd(row, loop) == 1) { RationalNumber rational = new RationalNumber(row, loop); list.Add(rational); } } for (int col = loop - 1; col >= 1; col -= jump) { // Add only if there are no common divisors // other than 1 if (gcd(col, loop) == 1) { RationalNumber rational = new RationalNumber(loop, col); list.Add(rational); } } } return list; } // Driver Code public static void Main(string[] args) { List<RationalNumber> rationals = generate(7); foreach(var rational in rationals) Console.Write(rational.toString() + ", "); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to implement the approachclass RationalNumber { constructor(numerator, denominator) { this.numerator = numerator; this.denominator = denominator; } toString() { if (this.denominator == 1) { return (this.numerator).toString(); } else { return (this.numerator).toString() + '/' + (this.denominator).toString(); } }}function gcd(num1, num2){ let n1 = num1; let n2 = num2; while (n1 != n2) { if (n1 > n2) n1 -= n2; else n2 -= n1; } return n1;}function generate(n){ let list = []; if (n > 1) { let rational = new RationalNumber(1, 1); list.push(rational); } for (var loop = 1; loop <= n; loop++) { var jump = 1; // Handle even case if (loop % 2 == 0) jump = 2; else jump = 1; for (var row = 1; row <= loop - 1; row += jump) { // Add only if there are no common divisors // other than 1 if (gcd(row, loop) == 1) { let rational = new RationalNumber(row, loop); list.push(rational); } } for (var col = loop - 1; col >= 1; col -= jump) { // Add only if there are no common divisors // other than 1 if (gcd(col, loop) == 1) { let rational = new RationalNumber(loop, col); list.push(rational); } } } return list;}// Driver Codelet rationals = generate(7);for (var rational of rationals) process.stdout.write(rational.toString() + ", ");// This code is contributed by phasing17 |
Output:
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, 1/6, 5/6, 6/5, 6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 7/6, 7/5, 7/4, 7/3, 7/2, 7
Time Complexity: O(n2)
Space Complexity: O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
