Skip to content

Instantly share code, notes, and snippets.

@suzuki-kei

suzuki-kei/README.md

Last active April 21, 2019 05:44
Show Gist options
  • Save suzuki-kei/9c28435c4f303b2ebe963a6b5fbd7fb6 to your computer and use it in GitHub Desktop.
Save suzuki-kei/9c28435c4f303b2ebe963a6b5fbd7fb6 to your computer and use it in GitHub Desktop.
Download ZIP
回文数 (Palindromic Number) を生成する
Raw
README.md

回文数 (Palindromic Number) を生成する.

定義

101 や 12321 のように左右反転しても同じである数を回文数という.

回文数の数

base 進数における N 桁の回文数の個数を考える. base 進数における N 桁の回文数は以下の制約を満たす必要がある.

  • 最上位桁は 0 以外 (N > 1 の場合)
  • 最上位から n 桁目と最下位から n 桁目が同じ値 (1 <= n <= N)

上記制約から, 回文数の数は次の式で求めることができる.

  • base 通り (N = 1 の場合)
  • (base - 1) * pow(base, floor((N - 1) / 2)) 通り (N > 1 の場合)

以下に具体例を挙げる.

  • base=2, N=2 の場合

    回文数の数 = (base - 1) * pow(base, floor((N - 1) / 2))
           = (2 - 1) * pow(2, floor((2 - 1) / 2))
           = 1 * pow(2, floor((2 - 1) / 2))
           = 1 * pow(2, floor(0.5))
           = 1 * pow(2, 0)
           = 1 * 1
           = 1 通り

  • base=2, N=3 の場合

    回文数の数 = (base - 1) * pow(base, floor((N - 1) / 2))
           = (2 - 1) * pow(2, floor((3 - 1) / 2))
           = 1 * pow(2, floor((3 - 1) / 2))
           = 1 * pow(2, floor(1.0))
           = 1 * pow(2, 1)
           = 1 * 2
           = 2 通り

  • base=10, N=3 の場合

    回文数の数 = (base - 1) * pow(base, floor((N - 1) / 2))
           = (10 - 1) * pow(10, floor((3 - 1) / 2))
           = 9 * pow(10, floor((3 - 1) / 2))
           = 9 * pow(10, floor(1.0))
           = 9 * pow(10, 1)
           = 9 * 10
           = 90 通り

回文数の生成

base 進数における N 桁の回文数は以下の手順で生成できる.

  • base 進数 floor((N + 1) / 2) 桁の数 x を生成する
  • x の最上位から floor(N / 2) 桁と x を左右反転した値を結合する
  • 結合した値が回文数となる

base=2, N=3 の場合は次のようになる.

  • 2 進数 2 桁の数 x を生成する 
    x = 10, 11
  • x の最上位から 1 桁と x を左右反転した値を結合する 
    x = 10 の場合: 1 と 01 を結合する -> 101
x = 11 の場合: 1 と 11 を結合する -> 111
  • 結合した値が回文数となる 
    101, 111
Raw
palindromic_numbers.py
from itertools import count
from itertools import islice
from itertools import product
def generate_palindromic_numbers(base):
"""
回文数を生成する.
Arguments
---------
base : int
基数を [2, 16] の範囲で指定する.
例えば 10 を指定すると 10 進数の回文数を生成する.
Yields
------
palindromic_number : str
回文数.
Raises
------
ValueError
base が [2, 16] に含まれない場合.
"""
if base not in range(2, 17):
raise ValueError
for number_of_digits in count(1):
numbers = _generate_palindromic_numbers(base, number_of_digits)
yield from numbers
def _generate_palindromic_numbers(base, number_of_digits):
"""
base 進数 number_of_digits 桁の回文数を生成する.
Arguments
---------
base : int
基数を [2, 16] の範囲で指定する.
例えば 10 を指定すると 10 進数の回文数を生成する.
number_of_digits : int
生成する回文数の桁数を指定する.
例えば 5 を指定した場合は 5 桁の回文数を生成する.
Yields
------
palindromic_number : str
回文数.
Raises
------
ValueError
base が [2, 16] に含まれない場合.
ValueError
number_of_digits が 1 未満の場合.
"""
if base not in range(2, 17):
raise ValueError
if number_of_digits < 1:
raise ValueError
numbers = _generate_numbers(base, (number_of_digits + 1) // 2)
to_palindrome = lambda digits: digits[:number_of_digits // 2] + digits[::-1]
numbers = map(to_palindrome, numbers)
numbers = filter(_is_number, numbers)
numbers = map(_digits_to_string, numbers)
yield from numbers
def _generate_numbers(base, number_of_digits):
"""
base 進数 number_of_digits 桁の数を生成する.
Arguments
---------
base : int
基数を [2, 16] の範囲で指定する.
例えば 10 を指定すると 10 進数の数を生成する.
number_of_digits : int
生成する数の桁数を指定する.
例えば 5 を指定した場合は 5 桁の回文数を生成する.
Yields
------
digits : tuple(int)
数.
digits[0] が最上位桁, digits[-1] が最下位桁となる.
"""
numbers = product(*[range(base)] * number_of_digits)
numbers = filter(_is_number, numbers)
yield from numbers
def _is_number(digits):
"""
digits が有効な数であるか判定する.
Arguments
---------
digits : tuple(int)
各桁の値を持つ tuple.
digits[0] が最上位桁, digits[-1] が最下位桁とする.
Returns
-------
bool
digits が有効な数である場合に True.
digits が 2 桁以上かつ最上位桁が 0 の場合は False.
"""
return len(digits) == 1 or digits[0] != 0
def _digits_to_string(digits):
"""
digits を文字列に変換する.
Arguments
---------
digits : tuple(int)
各桁の値を持つ tuple.
digits[0] が最上位桁, digits[-1] が最下位桁とする.
Returns
-------
str
digits の文字列表現.
"""
digit_to_string = lambda digit: "0123456789ABCDEF"[digit]
return "".join(map(digit_to_string, digits))
def main():
for palindromic_number in islice(generate_palindromic_numbers(base=8), 100):
print(palindromic_number)
if __name__ == "__main__":
main()
Raw
test_palindromic_numbers.py
import unittest
from itertools import islice
from itertools import product
from palindromic_numbers import generate_palindromic_numbers
from palindromic_numbers import _generate_palindromic_numbers
from palindromic_numbers import _generate_numbers
from palindromic_numbers import _is_number
from palindromic_numbers import _digits_to_string
class TestCase(unittest.TestCase):
def _get_palindromic_numbers(self, base, number_of_digits):
if base == 2 and number_of_digits == 1:
return (
"0", "1",
)
if base == 2 and number_of_digits == 2:
return (
"11",
)
if base == 2 and number_of_digits == 3:
return (
"101", "111",
)
if base == 8 and number_of_digits == 1:
return (
"0", "1", "2", "3", "4", "5", "6", "7",
)
if base == 8 and number_of_digits == 2:
return (
"11", "22", "33", "44", "55", "66", "77",
)
if base == 8 and number_of_digits == 3:
return (
"101", "111", "121", "131", "141", "151", "161", "171",
"202", "212", "222", "232", "242", "252", "262", "272",
"303", "313", "323", "333", "343", "353", "363", "373",
"404", "414", "424", "434", "444", "454", "464", "474",
"505", "515", "525", "535", "545", "555", "565", "575",
"606", "616", "626", "636", "646", "656", "666", "676",
"707", "717", "727", "737", "747", "757", "767", "777",
)
if base == 10 and number_of_digits == 1:
return (
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
)
if base == 10 and number_of_digits == 2:
return (
"11", "22", "33", "44", "55", "66", "77", "88", "99",
)
if base == 10 and number_of_digits == 3:
return (
"101", "111", "121", "131", "141",
"151", "161", "171", "181", "191",
"202", "212", "222", "232", "242",
"252", "262", "272", "282", "292",
"303", "313", "323", "333", "343",
"353", "363", "373", "383", "393",
"404", "414", "424", "434", "444",
"454", "464", "474", "484", "494",
"505", "515", "525", "535", "545",
"555", "565", "575", "585", "595",
"606", "616", "626", "636", "646",
"656", "666", "676", "686", "696",
"707", "717", "727", "737", "747",
"757", "767", "777", "787", "797",
"808", "818", "828", "838", "848",
"858", "868", "878", "888", "898",
"909", "919", "929", "939", "949",
"959", "969", "979", "989", "999",
)
if base == 16 and number_of_digits == 1:
return (
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "A", "B", "C", "D", "E", "F",
)
if base == 16 and number_of_digits == 2:
return (
"11", "22", "33", "44", "55", "66", "77",
"88", "99", "AA", "BB", "CC", "DD", "EE", "FF",
)
if base == 16 and number_of_digits == 3:
return (
"101", "111", "121", "131", "141", "151", "161", "171",
"181", "191", "1A1", "1B1", "1C1", "1D1", "1E1", "1F1",
"202", "212", "222", "232", "242", "252", "262", "272",
"282", "292", "2A2", "2B2", "2C2", "2D2", "2E2", "2F2",
"303", "313", "323", "333", "343", "353", "363", "373",
"383", "393", "3A3", "3B3", "3C3", "3D3", "3E3", "3F3",
"404", "414", "424", "434", "444", "454", "464", "474",
"484", "494", "4A4", "4B4", "4C4", "4D4", "4E4", "4F4",
"505", "515", "525", "535", "545", "555", "565", "575",
"585", "595", "5A5", "5B5", "5C5", "5D5", "5E5", "5F5",
"606", "616", "626", "636", "646", "656", "666", "676",
"686", "696", "6A6", "6B6", "6C6", "6D6", "6E6", "6F6",
"707", "717", "727", "737", "747", "757", "767", "777",
"787", "797", "7A7", "7B7", "7C7", "7D7", "7E7", "7F7",
"808", "818", "828", "838", "848", "858", "868", "878",
"888", "898", "8A8", "8B8", "8C8", "8D8", "8E8", "8F8",
"909", "919", "929", "939", "949", "959", "969", "979",
"989", "999", "9A9", "9B9", "9C9", "9D9", "9E9", "9F9",
"A0A", "A1A", "A2A", "A3A", "A4A", "A5A", "A6A", "A7A",
"A8A", "A9A", "AAA", "ABA", "ACA", "ADA", "AEA", "AFA",
"B0B", "B1B", "B2B", "B3B", "B4B", "B5B", "B6B", "B7B",
"B8B", "B9B", "BAB", "BBB", "BCB", "BDB", "BEB", "BFB",
"C0C", "C1C", "C2C", "C3C", "C4C", "C5C", "C6C", "C7C",
"C8C", "C9C", "CAC", "CBC", "CCC", "CDC", "CEC", "CFC",
"D0D", "D1D", "D2D", "D3D", "D4D", "D5D", "D6D", "D7D",
"D8D", "D9D", "DAD", "DBD", "DCD", "DDD", "DED", "DFD",
"E0E", "E1E", "E2E", "E3E", "E4E", "E5E", "E6E", "E7E",
"E8E", "E9E", "EAE", "EBE", "ECE", "EDE", "EEE", "EFE",
"F0F", "F1F", "F2F", "F3F", "F4F", "F5F", "F6F", "F7F",
"F8F", "F9F", "FAF", "FBF", "FCF", "FDF", "FEF", "FFF",
)
raise ValueError
def test_generate_palindromic_numbers_raises_ValueError_when_invalid_base_passed(self):
with self.assertRaises(ValueError):
next(generate_palindromic_numbers(base=1))
try:
next(generate_palindromic_numbers(base=2))
except:
fail()
try:
next(generate_palindromic_numbers(base=16))
except:
fail()
with self.assertRaises(ValueError):
next(generate_palindromic_numbers(base=17))
def test_generate_palindromic_numbers_when_base_2(self):
expected = (
*self._get_palindromic_numbers(base=2, number_of_digits=1),
*self._get_palindromic_numbers(base=2, number_of_digits=2),
*self._get_palindromic_numbers(base=2, number_of_digits=3),
)
actual = tuple(islice(generate_palindromic_numbers(base=2), len(expected)))
self.assertEqual(expected, actual)
def test_generate_palindromic_numbers_when_base_8(self):
expected = (
*self._get_palindromic_numbers(base=8, number_of_digits=1),
*self._get_palindromic_numbers(base=8, number_of_digits=2),
*self._get_palindromic_numbers(base=8, number_of_digits=3),
)
actual = tuple(islice(generate_palindromic_numbers(base=8), len(expected)))
self.assertEqual(expected, actual)
def test_generate_palindromic_numbers_when_base_10(self):
expected = (
*self._get_palindromic_numbers(base=10, number_of_digits=1),
*self._get_palindromic_numbers(base=10, number_of_digits=2),
*self._get_palindromic_numbers(base=10, number_of_digits=3),
)
actual = tuple(islice(generate_palindromic_numbers(base=10), len(expected)))
self.assertEqual(expected, actual)
def test_generate_palindromic_numbers_when_base_16(self):
expected = (
*self._get_palindromic_numbers(base=16, number_of_digits=1),
*self._get_palindromic_numbers(base=16, number_of_digits=2),
*self._get_palindromic_numbers(base=16, number_of_digits=3),
)
actual = tuple(islice(generate_palindromic_numbers(base=16), len(expected)))
self.assertEqual(expected, actual)
def test__generate_palindromic_numbers_raises_ValueError_when_invalid_base_passed(self):
with self.assertRaises(ValueError):
next(_generate_palindromic_numbers(base=1, number_of_digits=1))
try:
next(_generate_palindromic_numbers(base=2, number_of_digits=1))
except:
fail()
try:
next(_generate_palindromic_numbers(base=16, number_of_digits=1))
except:
fail()
with self.assertRaises(ValueError):
next(_generate_palindromic_numbers(base=17, number_of_digits=1))
def test__generate_palindromic_numbers_raises_ValueError_when_invalid_number_of_digits_passed(self):
with self.assertRaises(ValueError):
next(_generate_palindromic_numbers(base=2, number_of_digits=0))
try:
next(_generate_palindromic_numbers(base=2, number_of_digits=1))
except:
fail()
def test__generate_palindromic_numbers_when_base_2(self):
self.assertEqual(
self._get_palindromic_numbers(base=2, number_of_digits=1),
tuple(_generate_palindromic_numbers(base=2, number_of_digits=1)))
self.assertEqual(
self._get_palindromic_numbers(base=2, number_of_digits=2),
tuple(_generate_palindromic_numbers(base=2, number_of_digits=2)))
self.assertEqual(
self._get_palindromic_numbers(base=2, number_of_digits=3),
tuple(_generate_palindromic_numbers(base=2, number_of_digits=3)))
def test__generate_palindromic_numbers_when_base_8(self):
self.assertEqual(
self._get_palindromic_numbers(base=8, number_of_digits=1),
tuple(_generate_palindromic_numbers(base=8, number_of_digits=1)))
self.assertEqual(
self._get_palindromic_numbers(base=8, number_of_digits=2),
tuple(_generate_palindromic_numbers(base=8, number_of_digits=2)))
self.assertEqual(
self._get_palindromic_numbers(base=8, number_of_digits=3),
tuple(_generate_palindromic_numbers(base=8, number_of_digits=3)))
def test__generate_palindromic_numbers_when_base_10(self):
self.assertEqual(
self._get_palindromic_numbers(base=10, number_of_digits=1),
tuple(_generate_palindromic_numbers(base=10, number_of_digits=1)))
self.assertEqual(
self._get_palindromic_numbers(base=10, number_of_digits=2),
tuple(_generate_palindromic_numbers(base=10, number_of_digits=2)))
self.assertEqual(
self._get_palindromic_numbers(base=10, number_of_digits=3),
tuple(_generate_palindromic_numbers(base=10, number_of_digits=3)))
def test__generate_palindromic_numbers_when_base_16(self):
self.assertEqual(
self._get_palindromic_numbers(base=16, number_of_digits=1),
tuple(_generate_palindromic_numbers(base=16, number_of_digits=1)))
self.assertEqual(
self._get_palindromic_numbers(base=16, number_of_digits=2),
tuple(_generate_palindromic_numbers(base=16, number_of_digits=2)))
self.assertEqual(
self._get_palindromic_numbers(base=16, number_of_digits=3),
tuple(_generate_palindromic_numbers(base=16, number_of_digits=3)))
def test__generate_numbers_when_base_2(self):
self.assertEqual(
tuple(product(range(2))),
tuple(_generate_numbers(base=2, number_of_digits=1)))
self.assertEqual(
tuple(product(range(1, 2), range(2))),
tuple(_generate_numbers(base=2, number_of_digits=2)))
self.assertEqual(
tuple(product(range(1, 2), range(2), range(2))),
tuple(_generate_numbers(base=2, number_of_digits=3)))
def test__generate_numbers_when_base_8(self):
self.assertEqual(
tuple(product(range(8))),
tuple(_generate_numbers(base=8, number_of_digits=1)))
self.assertEqual(
tuple(product(range(1, 8), range(8))),
tuple(_generate_numbers(base=8, number_of_digits=2)))
self.assertEqual(
tuple(product(range(1, 8), range(8), range(8))),
tuple(_generate_numbers(base=8, number_of_digits=3)))
def test__generate_numbers_when_base_10(self):
self.assertEqual(
tuple(product(range(10))),
tuple(_generate_numbers(base=10, number_of_digits=1)))
self.assertEqual(
tuple(product(range(1, 10), range(10))),
tuple(_generate_numbers(base=10, number_of_digits=2)))
self.assertEqual(
tuple(product(range(1, 10), range(10), range(10))),
tuple(_generate_numbers(base=10, number_of_digits=3)))
def test__generate_numbers_when_base_16(self):
self.assertEqual(
tuple(product(range(16))),
tuple(_generate_numbers(base=16, number_of_digits=1)))
self.assertEqual(
tuple(product(range(1, 16), range(16))),
tuple(_generate_numbers(base=16, number_of_digits=2)))
self.assertEqual(
tuple(product(range(1, 16), range(16), range(16))),
tuple(_generate_numbers(base=16, number_of_digits=3)))
def test__is_number_when_one_digits_number_passed(self):
self.assertEqual(True, _is_number((0, )))
self.assertEqual(True, _is_number((1, )))
self.assertEqual(True, _is_number((2, )))
self.assertEqual(True, _is_number((3, )))
self.assertEqual(True, _is_number((4, )))
self.assertEqual(True, _is_number((5, )))
self.assertEqual(True, _is_number((6, )))
self.assertEqual(True, _is_number((7, )))
def test__is_number_when_two_digits_number_passed(self):
self.assertEqual(False, _is_number((0, 0)))
self.assertEqual(False, _is_number((0, 1)))
self.assertEqual(False, _is_number((0, 2)))
self.assertEqual(False, _is_number((0, 3)))
self.assertEqual(False, _is_number((0, 4)))
self.assertEqual(False, _is_number((0, 5)))
self.assertEqual(False, _is_number((0, 6)))
self.assertEqual(False, _is_number((0, 7)))
self.assertEqual(True, _is_number((1, 0)))
self.assertEqual(True, _is_number((1, 1)))
self.assertEqual(True, _is_number((1, 2)))
self.assertEqual(True, _is_number((1, 3)))
self.assertEqual(True, _is_number((1, 4)))
self.assertEqual(True, _is_number((1, 5)))
self.assertEqual(True, _is_number((1, 6)))
self.assertEqual(True, _is_number((1, 7)))
def test__digits_to_string_when_one_digits_number_passed(self):
self.assertEqual("0", _digits_to_string((0, )))
self.assertEqual("1", _digits_to_string((1, )))
self.assertEqual("2", _digits_to_string((2, )))
self.assertEqual("3", _digits_to_string((3, )))
self.assertEqual("4", _digits_to_string((4, )))
self.assertEqual("5", _digits_to_string((5, )))
self.assertEqual("6", _digits_to_string((6, )))
self.assertEqual("7", _digits_to_string((7, )))
def test__digits_to_string_when_two_digits_number_passed(self):
self.assertEqual("10", _digits_to_string((1, 0)))
self.assertEqual("11", _digits_to_string((1, 1)))
self.assertEqual("12", _digits_to_string((1, 2)))
self.assertEqual("13", _digits_to_string((1, 3)))
self.assertEqual("14", _digits_to_string((1, 4)))
self.assertEqual("15", _digits_to_string((1, 5)))
self.assertEqual("16", _digits_to_string((1, 6)))
self.assertEqual("17", _digits_to_string((1, 7)))
if __name__ == "__main__":
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment