Talk:Next highest int from digits: Difference between revisions
(→Next_permutation: add link.) |
|||
Line 27: | Line 27: | ||
==Next_permutation== |
==Next_permutation== |
||
Someone on Reddit r/coding posted a cryptic `std::next_permutation()`. Some searching shows that if it produces the next lexicographic permutation thn it is doing all the heavy lifting! [https://www.nayuki.io/page/next-lexicographical-permutation-algorithm Try this explanation]. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 11:52, 21 February 2020 (UTC) |
Someone on [https://www.reddit.com/r/coding/comments/f796q1/next_highest_int_from_digits/fi9uyx1?utm_source=share&utm_medium=web2x Reddit] r/coding posted a cryptic `std::next_permutation()`. Some searching shows that if it produces the next lexicographic permutation thn it is doing all the heavy lifting! [https://www.nayuki.io/page/next-lexicographical-permutation-algorithm Try this explanation]. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 11:52, 21 February 2020 (UTC) |
Revision as of 16:32, 21 February 2020
Task development
I got the bare question from an SO question My original attempt at Algorithm1 failed as it relied of Pythons permutation generator generationg in sorted order from initially sorted digits - this only worked if there were no duplicated digits.
After fixing and manual testing I started on the second algorithm and used the following kind of loop to find errors: <lang python> for i in range(1_000):
x = randint(10_000_000, 99_999_999) assert nexthigh1(x) == nexthigh(x), f"{x:>10} -> {nexthigh1(x):>10}, {nexthigh(x):>10}"
</lang>
My original closest_more_than() function was quite long, but explicit: <lang python>def closest_more_than2(n, lst):
"(index of), closest int to digit n from lst that is > n" i, dif = None, None n = int(n) for j, val in enumerate(int(x) for x in lst): if val > n: inew, difnew = j, val - n if difnew == 1: return inew elif dif is None or dif > difnew: i, dif = inew, difnew return i
</lang>
I had fun updating it, but needed the random test framework to flush out errors.
--Paddy3118 (talk) 11:12, 21 February 2020 (UTC)
Next_permutation
Someone on Reddit r/coding posted a cryptic `std::next_permutation()`. Some searching shows that if it produces the next lexicographic permutation thn it is doing all the heavy lifting! Try this explanation. --Paddy3118 (talk) 11:52, 21 February 2020 (UTC)