Skip to content

Instantly share code, notes, and snippets.

@tzaffi
Created September 29, 2014 06:14
Show Gist options
  • Save tzaffi/bc60f5a0fe82b7f56b2e to your computer and use it in GitHub Desktop.
Save tzaffi/bc60f5a0fe82b7f56b2e to your computer and use it in GitHub Desktop.
Solution to the generalized Josephus problem
def generalized_josephus(self, x):
# express x as a radix d number-sequence
rad_d = Radix.tuple(x, base=self.d)
# then apply the generalized josephus transformation to convert to a radix c number-sequence
rad_c = [self.alpha_vector[rad_d[0]-1]]
for dig in rad_d[1:]:
rad_c.append(self.beta_vector[dig])
# convert rad_c to a number and return
return Radix.number(rad_c, base=self.c)
class Radix:
@staticmethod
def number(x, base=10):
"""
Use Horner's method to convert (x)_base to a number.
:param x: an enumerable containing strings (such as a string)
:type x:
:param base:
:type base:
:return:
:rtype:
"""
if isinstance(x, str):
x = [int(c, base=base) for c in x]
y = 0
for digit in x:
y *= base
y += digit
return y
@staticmethod
def tuple(x, base=10):
"""
Returns the radix sequence of the number x as a tuple. Any non-integral remainder is left in
the least significant digit
:param x:
:type x:
:param base:
:type base:
:return:
:rtype:
"""
if x < 0:
raise ValueError("can only convert positive numbers to tuples of a given radix")
if x == 0:
return (0,)
res = []
while x > 0.0:
x, d = divmod(x, base)
res.append(d)
return tuple(reversed(res))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment