Posts: 6
Threads: 1
Joined: Jun 2021
Jun-20-2021, 06:43 PM
(This post was last modified: Jun-20-2021, 06:43 PM by lrn2codee.)
I'm trying to write a function that sorts a list of ints and letters in acending order (sort using unicode (ord())), using recursion with no loops. I am having trouble and I'm a little stuck. I tried using the code that was answered a while ago:
https://stackoverflow.com/questions/6092...-loop-in-p
but that one is using a for loop and works only for ints.
this is what i wrote til now but im getting into an infinite recurse, help please..
def sortlist(lst,n,i):
if (i == n-1):
if((ord(lst[0]) >= ord(lst[i])) and i>=1):
lst.insert(0,lst[i])
del lst[i+1]
i=0
return [lst[0]] + [sortlist(lst[1:],n-1,i+1)]
if n>1:
if((ord(lst[0]) >= ord(lst[i])) and i>=1):
lst.insert(0,lst[i])
del lst[i+1]
sortlist(lst,n,i+1)
else:
return lst[0]
lst = list(input())
n = len(lst)
i = 0
sortlist(lst,n,i)
print("".join(lst)) for this input example:
kd465b21
i will get this output:
Output: 124dk65b
instead of :
Output: 12456bdk
- (right unicode order)
for the code i posted i dont seem to notice the problem that i have, i am a begginer and ill be happy to learn what is my problem.
thank you very much for the helpers and the work is much appericated.
**
i would like to note that the code works for an input such as: 54321 ---> output: 12345
**
Posts: 6
Threads: 1
Joined: Jun 2021
I'm trying to write a function that sorts a list of ints and letters in acending order (sort using unicode (ord())), using recursion with no loops. I am having trouble and I'm a little stuck. I tried using the code that was answered a while ago:
https://stackoverflow.com/questions/6092...-loop-in-p
but that one is using a for loop and works only for ints.
so i worked on it a little but i cant seem to understand why it doesnt worrk for all the length:
def sortlist(lst,n,i):
if n==1:
return lst[0]
if i<=(n-1):
if i==(n-1) and n>1:
i=0
return [lst[0]] + [sortlist(lst[1:],len(lst)-1,i+1)]
if ord(lst[0])-ord(lst[1+i]) < 0 :
return sortlist(lst,len(lst),i+1)
if ord(lst[0])-ord(lst[1+i]) >= 0:
lst.insert(0,lst[1+i])
del lst[i+2]
return sortlist(lst,len(lst),i+1)
lst = list(input())
n = len(lst)
i = 0
sortlist(lst,n,i)
print("".join(lst)) for this input example:
kd465b21
i will get this output:
Output: 124dk65b
instead of :
Output: 12456bdk
- (right unicode order)
for the code i posted i dont seem to notice the problem that i have, i am a begginer and ill be happy to learn what is my problem.
thank you very much for the helpers and the work is much appericated.
**
i would like to note that the code works for an input such as: 54321 ---> output: 12345
**
Posts: 988
Threads: 15
Joined: Dec 2016
Jun-21-2021, 08:31 AM
(This post was last modified: Jun-21-2021, 08:31 AM by Axel_Erfurt.)
try
in_text = "kd465b21"
in_list = [x for x in in_text]
in_list.sort(key=str.lower)
print("".join(in_list)) Output: 12456bdk
Posts: 6
Threads: 1
Joined: Jun 2021
Jun-21-2021, 08:59 AM
(This post was last modified: Jun-21-2021, 08:59 AM by lrn2codee.)
(Jun-21-2021, 08:31 AM)Axel_Erfurt Wrote: try
in_text = "kd465b21"
in_list = [x for x in in_text]
in_list.sort(key=str.lower)
print("".join(in_list)) Output: 12456bdk
you did not read sir, im trying not to use sort() function,or any loops, im suppoused to use recursion only.
thank you for the effort but it does not help.
Posts: 1,566
Threads: 3
Joined: Mar 2020
Jun-21-2021, 09:12 AM
(This post was last modified: Jun-21-2021, 09:13 AM by bowlofred.)
1) Your function is return() ing information to the caller, but the main program ignores the data that is returned. It just prints the original lst object. If that information isn't necessary, then why are the return statements there? You should be printing the information you got from the function, not the data you called it with. Or you should make sure the function properly sorts the called list (but I don't think it's written to do that).
2) I think what you are trying to do is sort it so the lowest element goes to the front, then sort the rest of the list. So when you recursively call the sort again on line 9, I think you need to start from the beginning (of the now shorter list). So the i needs to be reset to zero for that call.
3) On line 9 sortlist returns a list. On line 3 sortlist returns an element of a list (probably a str the way you've used it). By returning different things, this complicates stuff. I recommend making it always return a list.
4) on line 9 you add two things together. The first is [lst[0]] . This is a list you create with a single element in it. The second is [sortlist(...)] . With step 3 above, this should always be a list. This means you're creating sublists. I think you mean to do something similar to return [lst[0]] + sortlist(...) .
lrn2codee likes this post
Posts: 6
Threads: 1
Joined: Jun 2021
(Jun-21-2021, 09:12 AM)bowlofred Wrote: 1) Your function is return() ing information to the caller, but the main program ignores the data that is returned. It just prints the original lst object. If that information isn't necessary, then why are the return statements there? You should be printing the information you got from the function, not the data you called it with. Or you should make sure the function properly sorts the called list (but I don't think it's written to do that).
2) I think what you are trying to do is sort it so the lowest element goes to the front, then sort the rest of the list. So when you recursively call the sort again on line 9, I think you need to start from the beginning (of the now shorter list). So the i needs to be reset to zero for that call.
3) On line 9 sortlist returns a list. On line 3 sortlist returns an element of a list (probably a str the way you've used it). By returning different things, this complicates stuff. I recommend making it always return a list.
4) on line 9 you add two things together. The first is [lst[0]] . This is a list you create with a single element in it. The second is [sortlist(...)] . With step 3 above, this should always be a list. This means you're creating sublists. I think you mean to do something similar to return [lst[0]] + sortlist(...) .
explantion:
what i was thinking of doing is, checking if the first unicode is bigger than the next one itll be replaced than i would call the function again but this time itll the check will be with the (i+1) in the list , if "i" reached the list's length itll insert the first character of the list and continue doing this until the length reaches 1 if i has reached 1 it means the last character is the biggest one and itll print it.
obviously somthing is going wrong, i cant understand how to fix it.
im reminding you that im not allowed to use for/while loops only recursion and not supposed to used sort() func. aswell.
to me it seems as if its not checking the last part of the list.
Posts: 988
Threads: 15
Joined: Dec 2016
OK, I did not read you will not use loop, maybe this is better
def sortlist(my_list):
def check_sorted(should_be_sorted, is_sorted):
new = []
if len(should_be_sorted) == 0:
return is_sorted
else:
x = min(should_be_sorted)
should_be_sorted.remove(x)
new.append(x)
return check_sorted(should_be_sorted, is_sorted + new)
return check_sorted(my_list, [])
lst = list(input())
print ("".join(sortlist(lst)))
lrn2codee likes this post
Posts: 988
Threads: 15
Joined: Dec 2016
If you have any questions then ask them here and not by private message.
You cannot use for / while loops, sort (), min.
What are you allowed to use at all?
Sounds like this is homework?
Posts: 6,202
Threads: 16
Joined: Feb 2020
Jun-22-2021, 06:48 PM
(This post was last modified: Jun-22-2021, 07:44 PM by deanhystad.)
I doubt this is in the "spirit" of the challenge, but it doesn't call sort or use any loops.
def recursive_sort(items):
if len(items) > 1:
min_value = min(items)
items.remove(min_value)
return [min_value] + recursive_sort(items)
return items It uses a sneak-cheat, borrowing the loop from min(). To make it less of a cheat you could do a recursive min.
def recursive_min(items):
if len(items) > 1:
a = items[0]
b = recursive_min(items[1:])
return a if a < b else b
return items[0]
def recursive_sort(items):
if len(items) > 1:
min_value = recursive_min(items)
items.remove(min_value)
return [min_value] + recursive_sort(items)
return items This highlights what you need for a completely recursive solution: Two recursions.
Sorts have two loops; an inner loop to find the lowest or highest remaining value, and an outer loop to split the list into sorted and unsorted values. Sometimes the two are very obvious like the bubbler and index loops in the bubble sort, or the search and insert loops in the insertion sort. Sometimes they can be really difficult to see like the quick but confusing heap sort or quick sort. But there are always two loops. One loop doing the sorting and another loop deciding what to sort.
Knowing that all you are doing is replacing a loop with recursion, you can rewrite (probably) any sort by simply replacing the loops with recursively computing the "loop" indices. Here is a recursive bubble sort.
def recursive_bubble(items, i=None, j=None):
if i is None:
i = len(items)-1 # No items are sorted
j = 0
if i >= 0:
if j < i:
# bubble largest unsorted item to end
if items[j] > items[j+1]:
items[j], items[j+1] = items[j+1], items[j]
recursive_bubble(items, i, j+1)
else:
# Move the unsorted/sorted pivot toward the front of the list
recursive_bubble(items, i-1, 0) The i "loop" splits the list into sorted and unsorted items. I starts at the end and moves toward the front of the list to eliminate multiple len() calls. The j "loop" is the bubbler. It pushes the largest remaining value toward the end of the list. Two loops. One to sort the remaining values (j) and one to decide which values need to be sorted (i).
Hopefully now you can see why your code does not work. Where are your "loops"? Where is the pivot loop? Where is the sorter loop?
Posts: 988
Threads: 15
Joined: Dec 2016
(Jun-22-2021, 06:48 PM)deanhystad Wrote: Hopefully now you can see why your code does not work. Where are your "loops"? Where is the pivot loop? Where is the sorter loop?
He said he was not allowed to use loops, sort, min.
|