Derangements¶
Derangements is the arrangement of the letters in such a way that no letter goes to its original position
In [1]:
# dictionary for memoization
subFact_memoization = {}
# function for sub-factorial using recursion
def subFact(n, memoize)-> int:
if n <= 3:
return n-1
if n in subFact_memoization.keys():
return subFact_memoization.get(n)
ans = (n-1)*(subFact(n-1, False)+subFact(n-2, False))
if memoize:
subFact_memoization[n] = ans
return ans
Words on which we will test our code¶
In [2]:
words = ['MATH', 'LILAC', 'BOTTLE']
In [3]:
# function to check for derangements
def isDerangement(arr_original, arr_new):
n = len(arr_new)
if n != len(arr_original):
return False
for i in range(n):
if arr_new[i] == arr_original[i]:
return False
return True
In [4]:
# auxillary array
static_arr = []
derangement_list = []
def derange(mutable_arr, limit, index = 0):
if len(derangement_list) >= limit:
return
if index == len(static_arr)-1:
if mutable_arr not in derangement_list:
if isDerangement(static_arr, mutable_arr):
derangement_list.append(mutable_arr[:])
return
for i in range(index,len(mutable_arr)):
t = mutable_arr[index]
mutable_arr[index] = mutable_arr[i]
mutable_arr[i] = t
derange(mutable_arr, limit, index+1)
t = mutable_arr[index]
mutable_arr[index] = mutable_arr[i]
mutable_arr[i] = t
Driver code¶
In [5]:
if __name__ == "__main__":
for word in words:
static_arr = list(word)
# this is where the magic happens
derange(static_arr[:], limit = subFact(len(word), True))
print(f'Number of derangements for {word} is {len(derangement_list)}:')
for i in derangement_list:
print(''.join(i))
print()
derangement_list = []
Number of derangements for MATH is 9: AMHT ATHM AHMT TMHA THMA THAM HTAM HTMA HMAT Number of derangements for LILAC is 12: ILACL ILCLA IACLL ICALL ALICL ALCLI ALCIL ACILL CLILA CLAIL CLALI CAILL Number of derangements for BOTTLE is 84: OBLETT OBELTT OTBLET OTBETL OTLBET OTLEBT OTLETB OTELTB OTELBT OTEBTL OLBETT OLEBTT OELBTT OEBLTT TBOLET TBOETL TBLOET TBLEOT TBLETO TBELTO TBELOT TBEOTL TTBOEL TTBLEO TTBEOL TTOBEL TTOLEB TTOEBL TTLOEB TTLBEO TTLEBO TTLEOB TTEOBL TTELOB TTELBO TTEBOL TLBOET TLBEOT TLBETO TLOBET TLOEBT TLOETB TLEOTB TLEOBT TLEBOT TLEBTO TEBLTO TEBLOT TEBOTL TELBTO TELBOT TELOBT TELOTB TEOLTB TEOLBT TEOBTL LTOBET LTOEBT LTOETB LTBOET LTBEOT LTBETO LTEBTO LTEBOT LTEOBT LTEOTB LBOETT LBEOTT LEBOTT LEOBTT ETOLTB ETOLBT ETOBTL ETLOTB ETLOBT ETLBOT ETLBTO ETBLTO ETBLOT ETBOTL ELOBTT ELBOTT EBLOTT EBOLTT