# perms.py
# print all permutations of elems string

import random
from itertools import permutations 


def permute1(elems):
  perm(elems, 0, len(elems))

def perm(elems, left, right):
  if left == right:
    print(elems)
  else:
    for i in range(left, right):
      elems[left], elems[i] = elems[i], elems[left]
      perm(elems, left+1, right)
      elems[left], elems[i] = elems[i], elems[left]


def permuteY(elems):
  if len(elems) <= 1:
    yield elems
    return
  for p in permuteY(elems[1:]):
    for i in range(len(elems)):
      yield p[:i] + elems[0:1] + p[i:]


def shuff(elems):
  n = len(elems)
  for i in range(n-1, 1, -1):
    rIdx = random.randint(0, i-1)
    elems[i], elems[rIdx] = elems[rIdx], elems[i]



if __name__ == "__main__":
  elems = list(input("s? "))
  print("list:", elems)

  print("Permutes")
  permute(elems.copy())

  print("\nPermutesY")
  for p in permuteY(elems.copy()):
    print(p)
  permGen = permuteY(elems.copy())
  print("Next:", next(permGen))
  print("Next:", next(permGen))
  print("Next:", next(permGen))

  print("\nPermutationsY")
  for p in permutations(elems.copy()):
    print(p)
  permGen = permutations(elems.copy())
  print("Next:", next(permGen))
  print("Next:", next(permGen))
  print("Next:", next(permGen))

  print("\nShuffle")
  els = elems.copy()
  shuff(els); print(els)
  shuff(els); print(els)
  shuff(els); print(els)

  print("\nrandom Shuffle")
  els = elems.copy()
  random.shuffle(els); print(els)
  random.shuffle(els); print(els)
  random.shuffle(els); print(els)