Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Determine the Order by Kurush
import itertools
# I have implemented 3 different solutions to this problem.
# 1) The first one is the method of permutations. For each of n! permutations
# there is a check if this permutation is correlated with the given strings.
# In case of a partial order additional function GetStringFromPartialOrder is used.
# This method works well with relatively small amount of letters (< 10 different letters in the given strings).
# 2) The second method is using successive elimination of the first elements. Initial list of alphabet has to be
# sorted in accordance with partial order sorting rule (ordinary sorting). It allows to obtain correct string even if
# the first element can't be determined.
# 3) The third method is using sorting table. In the first iteration all relations between symbols are obtained.
# After that CompareSymbols function is used for ordinary sorting.
def checkio(data):
#return PermutationMethod(data)
#return SuccessiveEliminationMethod(data)
return SortingTableMethod(data)
def PermutationMethod(data):
ListAlphabet = GetListAlphabet(data)
AcceptedPermutationsList = []
for PermutationList in itertools.permutations(ListAlphabet):
Accepted = True
for OrderString in data:
ListOfSymbols = list(OrderString)
Accepted = Accepted and AreListsCorrelate(PermutationList, ListOfSymbols)
if Accepted: AcceptedPermutationsList.append(PermutationList)
if len(AcceptedPermutationsList) == 1:
return "".join(AcceptedPermutationsList[0])
else:
return GetStringFromPartialOrder(AcceptedPermutationsList)
def SuccessiveEliminationMethod(data):
ResultString = ""
ListAlphabet = sorted(GetListAlphabet(data))
while ListAlphabet != []:
for Symbol in ListAlphabet:
Accepted = True
for OrderString in data:
if (Symbol in OrderString) and (OrderString[0] != Symbol):
Accepted = False
break
if Accepted:
ResultString += Symbol
for i in range(len(data)):
if Symbol in data[i]:
data[i] = data[i].replace(Symbol, "")
ListAlphabet.remove(Symbol)
break
return ResultString
def SortingTableMethod(data):
def CompareSymbols(Left, Right):
if Right in SymbolOrder[Left][0]: return 1
elif Right in SymbolOrder[Left][1]: return -1
else:
if Left > Right: return 1
else: return -1
ListAlphabet = sorted(GetListAlphabet(data))
SymbolOrder = {}
for Symbol in ListAlphabet:
SymbolOrder[Symbol] = [set(), set()]
for Symbol in ListAlphabet:
for OrderString in data:
if Symbol in OrderString:
ListOfSymbols = list(OrderString)
for StringSymbol in ListOfSymbols:
if ListOfSymbols.index(Symbol) > ListOfSymbols.index(StringSymbol):
SymbolOrder[Symbol][0].add(StringSymbol)
if ListOfSymbols.index(Symbol) < ListOfSymbols.index(StringSymbol):
SymbolOrder[Symbol][1].add(StringSymbol)
Changed = True
while Changed != False:
Changed = False
for Symbol1 in ListAlphabet:
LenOld1 = len(SymbolOrder[Symbol1][0])
LenOld2 = len(SymbolOrder[Symbol1][1])
for Symbol2 in ListAlphabet:
if Symbol2 in SymbolOrder[Symbol1][0]:
SymbolOrder[Symbol1][0] = SymbolOrder[Symbol1][0] | SymbolOrder[Symbol2][0]
if Symbol2 in SymbolOrder[Symbol1][1]:
SymbolOrder[Symbol1][1] = SymbolOrder[Symbol1][1] | SymbolOrder[Symbol2][1]
LenNew1 = len(SymbolOrder[Symbol1][0])
LenNew2 = len(SymbolOrder[Symbol1][1])
if (LenOld1 != LenNew1) or (LenOld2 != LenNew2):
Changed = True
ListAlphabet = sorted(ListAlphabet, CompareSymbols)
return "".join(ListAlphabet)
def GetListAlphabet(data):
Alphabet = set()
for OrderString in data:
for Symbol in OrderString:
Alphabet.add(Symbol)
ListAlphabet = []
for Symbol in Alphabet:
ListAlphabet.append(Symbol)
return ListAlphabet
def AreListsCorrelate(List1, List2):
for Element1 in List2:
for Element2 in List2:
if ((List1.index(Element1) <= List1.index(Element2) and List2.index(Element1) > List2.index(Element2)) or
(List1.index(Element1) > List1.index(Element2) and List2.index(Element1) <= List2.index(Element2))):
return False
return True
def GetStringFromPartialOrder(List1):
PartialList = []
PartialOrderString = ""
for i in range(len(List1[0])):
IsPartial = False
for j in range(len(List1)):
if List1[0][i] != List1[j][i]:
PartialList.append(List1[0][i])
IsPartial = True
break
if not IsPartial:
if PartialList == []:
PartialOrderString += List1[0][i]
else:
PartialOrderString += "".join(sorted(PartialList))
PartialOrderString += List1[0][i]
PartialList = []
if PartialList != []:
PartialOrderString += "".join(sorted(PartialList))
return PartialOrderString
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio(["acb", "bd", "zwa"]) == "zwacbd", \
"Just concatenate it"
assert checkio(["klm", "kadl", "lsm"]) == "kadlsm", \
"Paste in"
assert checkio(["a", "b", "c"]) == "abc", \
"Cant determine the order - use english alphabet"
assert checkio(["aazzss"]) == "azs", \
"Each symbol only once"
assert checkio(["dfg", "frt", "tyg"]) == "dfrtyg", \
"Concatenate and paste in"
May 18, 2013
Comments:
