Are THESE Better Than Lists?? - The Josephus Permutation

⭐ Join my Patreon: / b001io
💬 Discord: / discord
🐦 Follow me on Twitter: / b001io
🔗 More links: linktr.ee/b001io
Background Music:
Mood by Alex-Productions | onsound.eu/
Music promoted by www.free-stock...
Creative Commons / Attribution 3.0 Unported License (CC BY 3.0)
creativecommon...
Slowly by Tokyo Music Walker | / user-356546060
Music promoted by www.free-stock...
Creative Commons / Attribution 3.0 Unported License (CC BY 3.0)
creativecommon...

[@MrAnonEMoss]

There may be a caveat here. According to the docs, the time complexity for deque.rotate(k) is O(k). In this case, when k

[@kikivoorburg]

Unless I’ve missed something, it would be possible to handle k > n/2 by counting n-k items backwards from the end of the list. That would make n/2 the worst-case. I’m not sure if you already realised that, but I thought I’d mention it anyway since your comment didn’t make it explicit. I could also be wrong, please correct me if I am!

[@MrAnonEMoss]

@@kikivoorburg Yeah, I was kind of thinking along those lines, but I didn't want to put it in my comment because I wasn't 100% sure. But yeah, I think you're correct on that

[@MrAnonEMoss]

And I ran the code on my computer. In the situation presented in the video, when we have 1,000,000 soldiers and k=3, the amount of time it took on my computer was 0.14 seconds. When I ran it with 1,000,000 soldiers and k=500,000, it took 77.25 seconds

[@antonhelsgaun]

​@@kikivoorburgO(n/2)=O(n), though

[@valdrich472]

is there a way to 'pop' multiple items from a list? In R I'd append (of sorts) every k-th element from the array, after accounting for the leftover elements from the previous loop. This would be even faster for k

[@yuu-kun3461]

To be pedantic about it, the pythonic "list" in a dynamic array which is also known as a vector. Whereas the deque is a type of doubly linked list which is called "list" for short, compaired to the vector.

[@DeclanMBrennan]

Not just pedantry - I think this can be confusing for new developers. Alas the list terminology is misused in some other languages as well, so it's probably too embedded to be changed at this point.

[@gangulic]

Coming from C language I’ve always thougth python list is same as a linked list just with some additional perks

[@AG-ur1lj]

@@DeclanMBrennanthe irony kills me. I’ve listened to engineers drone on for hours about the importance of “good names,” yet the industry as a whole is addicted to the foot-gun. And it just keeps going. Google finds some peculiar characteristic of LLMs? “Hey guys, let’s call them ‘hallucinations’! That sounds really clever and creative. It couldn’t possibly create problems and confusion in the future.” Nice job! Good thing a company that specializes in word search was on that one👍🏻

[@Thekingslayer-ig5se]

You have no idea about how helpful and useful you are for people like me. I’m a data analyst who predominantly uses Python and this is super super useful. God bless you ❤

[@anuragpant2632]

Hey can u tell me what is the use case of this algorithm

[@rembautimes8808]

I like this content and it’ll be good to see use cases of deque so we know when to apply it

[@thebeastsclips]

​@@anuragpant2632the deck is faster for larger input/array.

[@austinnar4494]

You're one of the few programming KZbinrs I've found that strike the balance of being approachable for beginners and don't gloss over best practices and the relevant CS concepts that people need to grow (time complexity, data structures, etc). Love the content

[@saintjonny]

the font is brass mono cozy for those who are wondering

[@mithilbhoras5951]

One of the best videos ever. Instead of a dry approach, you explained Lists, deques AND the Josephus permutation in a fun way where you gradually build upon the solution one step at a time. Seeing the code getting improved was magical and I felt like I learnt something useful that I won't forget. Two thumbs up!

[@machado8127]

A while back I derived a formula to find the last guy in this problem after watching a numberphile vid about it. the formula is f(x)= 2(x-2^(floor(log'base2'(x)))) +1. I plotted it in desmos and it looked pretty cool.

[@b001]

I plotted it in desmos and that's really interesting. That's for k=2, right? I wonder if there are formulas for other k-values? Thanks for sharing!

[@maxsurman7838]

​@@b001perhaps this is too simple, but just replace the 2 values with k?

[@machado8127]

@@b001Well I tried deriving one but couldn’t, and when I looked online, there were none like f(x)= formula style. So if someone finds it they gonna get famous.

[@poki6041]

​@@machado8127i used chat gpt i got this x = \frac{k - 1}{2} + 2^n k-1/2+2^n But ithink its shit lol

[@Haagimus]

I've never heard of deques before but as soon as you explained how they work, I knew you were talking about a linked list! Wonderful video

[@GetPsyched6]

This video really helped me understand deque. Are you planning to go through the rest of the data structures other than the ones you have covered?

[@b001]

Potentially, eventually!

[@BeriBGood]

I really enjoy your videos, no useless flashy intro, straight to the point and for me a lot of unique content I didn't see anywhere else. Thank you very much

[@tylerbakeman]

List is more of a generalization of a linear structure (specifically Sequences or Tuples), that allows for appending / removing- Queues do this as well, (and are also generalized: as there are different types of queues), but could be represented by a Tree, rather than a Tuple- The tree is a “Fan of degree-1”, for queues and stacks- and is better for appending / removing elements, but removes random access to those elements. The queue gets a reference to a “Head” and “Tail”: tails can only be added to; whereas, heads technically allow removal and adding (in a ~singly directed graph). The stack gets just a “Head” reference instead to add/ remove. For ~doubly directed graphs (some might consider this “undirected”, but I think there’s a difference), then there is more symmetry, and you can add / remove from either side. Also, you can iterate forwards and backwards (instead of just forwards). It uses quite a bit more memory though PS: (Memory optimization idea) Each directed edge is an Object reference can be replaced with an integer reference to a hash-code that will map to a unique object in an outside list (this is exactly how a hashmap works) Technically a hashmap stores Pairs, in a sublist, to avoid “collision” with the hashes- and we should do the same. Cheers

[@tylerbakeman]

Also. Lists from Tuples, are great because they allow for random access. So choose your data structure wisely.

[@HarryC4615]

Hi b001! Your videos are really well made and clear. I wondered what software/tools do you use to create your videos and the animations. Keep up the good work.

[@ksulimma]

As others noted when using the deque hte complexity becomes O(n*k). The same can be achieved by looping over an array with two indexes, compacting the array while searching it. E. g. for k=3 you would do copy, copy, skip, copy, copy, skip. This should be asymptotically the same but have better constants. For large k a red-black-tree, splay-tree or a skip-list would be much, much faster.

[@DrummingDivingPythonProgrammer]

I've watched a few of your videos, and while they were interesting, they were not quite enough to motivate me to give you a subscribe. This one got it. That's incredible.

[@johnmurphy9727]

It’s wonderful to see the deque or linked list being utilized in python!

[@soyitiel]

One thing to keep in mind, though, is cache invalidation (which granted, if we're using python, it might be the least of our problems). Depending on the sample size of our data, the deque approach might be less efficient than the array one, or vice versa.

[@dogslife4831]

Very clever use of Mod Operation

[@FriendlyCodeBuddy]

Your video is great, as always! I am a huge fan of this type of content.

[@RAyLV17]

Oh wow. Recently discovered your channel through your list comprehension video. Your explanation style amazing! Subbed!

[@yannisbekiaris]

yeah man that presentation is amazing! MANY MANY THANKS

[@devonharvey8414]

You’re explaining, voice and teaching are very helpful and informative, you earned a new subscriber and I’m hoping to see more content like this, I’m gonna start learning python soon and I’m gonna need content like this

[@Spamuse-w3i]

wow such a great video!! could you please tell me which software or where to edit those array animations you're making in your videos. Thanks in advance :))

[@GenarDarwish]

Your videos are very understandable and clear. I suggest you create a full course on Python. Thank you.

[@MiguelRojas-ud5cm]

I found your channel and it's one of the best I've ever seen , thank you for your videos i hope you can cover more topics and explain them for beginners like me 🎉

[@remipelletier5117]

Great video as always! Keep them coming please! Just want to add that from some simple tests I've run, if you only require to pop one (or very few?) items, d = deque(array) takes more time than the popping saves. In other words, the conversion to deque outweighs the benefits of deque popping. However, obviously if you have n popping operations to do, then the conversion time becomes negligible in comparison.

[@ladyravendale1]

Nice vid, though I wouldn’t say outright better is correct. Like everything, there is a trade off. Lists: O[n] worst case removal, O[1] lookup. Deques: O[1] removal, O[n] worse case lookup. There is also cache coherence to think about, which lists are very good at thanks to be continuous in memory, while deques are very bad thanks to being spread in memory. As usual, the best thing to do is measure, try something different, measure again.

[@GfoxSim]

I really enjoy your videos.

[@FormatException]

I'd be curious of the memory implications of this. deque sounds like a doubly linked list so rather than working with an array of primitives there is a large number of objects. Now, granted my background is C++/C#/Java so I'm willing to accept that I'm wrong completely in my assumptions, but I would assume that using the code would result in a large number of objects on the heap. Is there a significant difference in memory allocations?

[@the_cheese_cultist]

there are multiple implementations of deque. a linked list is one of them, but it's not the most common. most deque implementations used allow constant index access. you can look at the Wikipedia page for more info.

[@julsmanbr8152]

There are no primitives in Python, even things like integers and strings are all encapsulated by objects. So in the end, regular lists and deques are both objects that store other objects.

[@karreevn9085]

Yo, i really love this CP contents, thank you so much for this. Hope you can do other video relating to standard libraries such as Pandas or Numpy :DDD

[@pranavakailash8751]

To be honest, I had never considered this Data Structure. Thank you @b001 for the video. Very informative and helpful!

[@oro5421]

Ok now I’m pretty sure c++ has a completely different implementation of deque that is far more logical to call it a double ended queue. I’ve always thought that they are the same!

[@hotwheelz5686]

It is just a Linked List, also I remade the solution in C++, without the Linked Lists though, just to see how much faster C++ was, and it was 26 seconds for 1 million elements (with me removing the element), without removing the element, and just adding the element to the return array, it is 34 milliseconds.

[@XirevWoW]

@@hotwheelz5686 By not removing the item from the list, did you account for the fact that you're now 1 step behind where you would otherwise be if you had removed the item? Since when you remove an item, what was 1 index ahead of you, is now the index you are currently on. And since you are not removing the item, won't you just rotate around the list to the same positions? And when are you determining that you have "killed" all of the men? Since he's checking for when the list is empty to stop looping.

[@hotwheelz5686]

@@XirevWoW I indeed did forget about that, although it would not have any implication with the time of soultion, although it would be an incorrect solution, but I was more just looking at the time difference between C++ and Python, and I remade it in like 5 mintues and called it good lol, but not decrementing the index would create an incorrect solution

[@kvetter]

This code is relying upon an implementation detail of deque. Deques only guarantees O(1) for push_front() and push_back()--there's no such guarantee for rotate() or arbitrary deletion. A link-list implementation of deque has fast rotation, but another common implementation of an array of dynamic arrays (aka array deques) has very slow rotations.

[@hifive5067]

I had seen usage of deque in DSA course in the past, but I had trouble understanding why it was used back then. Now it's pretty clear :-) Cheers!

[@kenhaley4]

I've used a deque before, but I didn't know about rotate. Looks like the perfect data structure for this problem.

[@longbranchgooberdapple2238]

tldr: proper data structure for your problem is very important. It could make a 100x difference in calculation time and/or complexity.

[@compucademy]

Interesting that popping the array correctly models the problem, which is not immediately obvious from the visual representation.

[@Jelqmaxxer-f5b]

These videos make me so excited to start my career

[@chri_pierma]

Your videos are so good! Are you using a specific textbook to get these information from?

[@thefanboy3285]

Finding about that new form of linked list tingles my brain 😁😁 BTW, if I wanted to learn python on my own through the official docs, how would I do that ? I mean no offense but python's docs is the _most messiest_ docs I've ever seen, just right after Microsoft's VBA docs. (I guess that's why they implemented it to MSExcel lol)

[@plekkchand]

This is beautifully done.

[@goforit2085]

Thing is that if i m not wrong, each element of the deck will take way more memory as he has an integer (32 bits), and 2 pointers (128 bits) wich give us 160 bits in emory for one element instead of 32 bits for an array. So as my college teacher says, the perfect algorithm doesn't exists, its just a story of memory cost and temporal cost balance.

[@nits_koh]

The video is so clean. What do you use to create your animation /illustration?

[@Spamuse-w3i]

Same question. do you know any animation software where we can edit those Array like animations ???

[@eldaiblol1492]

I know it might not fetch as many views as the simpler, common Videos, but please keep posting about these more advaced topics. Theres enough beginner coding, we need some good stuff :) thank you!

[@Miryxem]

Love your videos! could you do some custom exception errors, or decorators por functions ?

[@stacksmasherninja7266]

Yeah you can't sort deques in O(nlogn). You also can't search a sorted deque in O(logn).The continuous memory list is pretty handy for this. You should add this caution at the end in my opinion.

[@AnubhavSharma-e6r]

Not sure how. But somehow i found myself here. And now I have my new favourite coding channel.

[@danda_legenda]

Cool video, bro! What color theme do you use for coding? It looks fire

[@xdanic3]

Seems like SynthWave '84 to me

[@danda_legenda]

@@xdanic3 thank you

[@Aborrajardo]

Awesome content and explanation! Thanks!

[@xXYourShadowDaniXx]

When you showed the memory operations for deque I realized: Oh thats a doubly linked list, cool

[@filipkrawczyk9630]

Naming this data structure deque is really confusing to me, because it is essentially a double linked list. In C++ for example deque is implemented using a dynamic array and it allows for element access in constant time as well as appending and popping from both sides. So to compare time complexity (C++ vs python): Append/pop (any side): O(1) (amortized I believe) vs O(1) Remove given element: O(n) vs O(1) Access random index: O(1) vs O(n) So it's a completely different structure. Really weird naming decision.

[@ajflink]

Whenever working with strictly a list of numbers, I always use the array module, especially with integers. deque seems more inviting to me now as the docs made me think: In what scenario would I ever use this? Also, if you are just going to pop the last element of a list (i.e. the rightmost) throughout a process if at all, it seems like deque may be a bit redundant. However, most other scenarios, deque seems like the better option unless memory is a huge thing you need to consider.

[@varshard0]

Instant subscribed

[@joshuat6124]

Good stuff! Subbed!

[@CoderIQBE]

Hi! I quickly want to ask what vs code theme you're using as I realy like the coloring.

[@sohailraufi1630]

Hey Your videos are amazing. Can you tell me the theme you are using in your IDE?

[@d3f3kt57]

What's the name of the monospace font you use? Looks pretty clean.

[@saintjonny]

if you get to know let me know as well. thanks

[@saintjonny]

after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy

[@d3f3kt57]

Thank you! You have the patience of a saint indeed. @@saintjonny

[@saintjonny]

@@d3f3kt57welcome

[@CaptMirage]

Josephus : casually takes out his laptop and codes a python program that takes 2 mins to make sure he survives others : what the hell is he doing b001 : hey would you mind if i barrow that idea for a video?

[@nubbieeee]

What vs code theme are you using? I really love the look of the syntac highlighting and vibrancy. Also, nice video about deque :D

[@xdanic3]

Looks like SynthWave '84

[@b001]

SynthWave’84

[@rami5801]

Might be a bit of a meme question but what VSCode theme are you using? It kinda looks like Tomorrow Night Blue

[@m7b774]

I just watched class in 1 minute and I like how u explain class function can u do python for beginners

[@Idan_Nesimov]

Amazing.. great job !

[@malchemis]

Why is your code terminal so cool ?

[@Felle2002]

Isn't the time complexity O(N/2) when going through a doubly link list/deque, there by making the time complexity O(N*(N/2)) and not O(n)? And the gains come from not having to shift all the data in memory and instead just having to change a single pointer? Or am I thinking wrong somehow?

[@Felle2002]

Wait just realised that I'm wrong since we will have rotated the list so you just have to go 3 more spaces in the while loop

[@temptedtrevor8498]

I'm waiting for the person who always comments a one-liner solution.

[@shakils1921]

Thanks man

[@irina_divine]

there is a way to crunch this algorithm down to 1 line

[@gentlemanbirdlake]

Rotate the deque like a DJ on the decks, scratchin’ left or right for the choice cuts

[@hamzahakoun1072]

more videos likes this please

[@NStripleseven]

So instead of O(n^2) it’s O(n*k), for n rotate operations which take (I think) k time to complete?

[@dawidsz56]

Question about list example, I have 2 lists, arr1 is numbers, arr2 is chars arr1 = [1, 2, 3, 3.14, 4, 5] arr2 = ["a", "b", "c", "d", "e"] I want to combine them, but... Should I user rr3 = arr1 + arr2 or? arr3 = arr1.copy() + arr2.copy() which one is better?

[@digitalmachine0101]

Good information

[@rohullahalavi]

tanks

[@konstantinbachem9800]

here is my solution using lists :) it is 4x faster from time import perf_counter def solution(array,n): result=[] offset=n-1 while l: offsetneu=(offset-len(l))%n result.extend(l[offset::n]) del l[offset::n] offset=offsetneu return result k=1000000 n=3 l=list(range(1,k+1)) start=perf_counter() sol=solution(l,n) print(perf_counter()-start) print(sol[-100:])

[@OmegaMetorOutside]

When seeing the rotation, my first thought is just why is traversing through pointers until the head is at the right one any faster than o(n), making it still overall o(n^2)?

[@Chris-op7yt]

why would you need memory structures for this at all? simple iterative function mod highest number and loop highest number times in total

[@hk254lyt8]

I hope one day I’ll be this good in algorithms😢

[@ngspace9829]

You will!

[@AilentRed]

very helpful !

[@igris_tec]

Yeah, but how do I make normal permutations? (ABC)!

[@maniagames94]

Nice video, brow!

[@taejimcap]

holllly molly WTF......., this really helped me while True: print("thank you")

[@sabrysm]

May I ask how did you do this animation?

[@ike__]

For the array why not just use the range function?

[@rkdeshdeepak4131]

Wouldn't rotate be O(n) now?

[@delofj]

I never though yet another data structure existed in python Is there more unknown data structure in python hidden from us like that ?

[@makedits]

which font do you use brother?

[@saintjonny]

after 8 hours of searching for this font and opening over 100 tabs i found, its called brass mono cozy

[@toanvong3825]

Cool but that actually leads to the complexity of O(n * k) which is terrible when k = n. There actually is a data structure that can solve the problem in O(n * log(n)) which is Binary Indexed Tree or Fenwick Tree. I wish you could make a video on solving this problem using those proposed data structure, that would be super cool 😎😎.

[@antonhelsgaun]

Binary index tree sounds oof, though

[@antonhelsgaun]

So why not just use a linked list?

[@braydenmchan]

This "deque" is almost like a doubly linked list!

[@b001]

Yep, that’s how it’s implemented in Python

[@braydenmchan]

@@b001 ahhh okay that makes sense. It's cool that Python has an implementation of this. Look at that, learning something new every day!

[@sudhenduahir802]

Whats the font being used anyone aware.. I find it pretty cool...

[@saintjonny]

after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy

[@reeti5958]

I am still confused why you are rotating elements in deque? It is a double ended queue, why bring the element in head to delete it? Just traverse to the element and remove it from there. I am confused, is there a difference in this or something? I haven't used queues and stacks in python, so..

[@nickburggraaf3977]

I hope Josephus knew about deques as well

[@Cookie-mv2hg]

It's another year of AOC, the deque is so helpful if you want to get to the leader board

[@Артем-у8и1щ]

That solution is still really slow. Rotating deque still takes O(n).

[@Tyrant369]

What theme and font is this?

[@babanesma]

Keep up 👏

[@coopernik]

do more of solving a problem to teach a concept

[@bridgeboo3031]

why not show how deque performs with a million soldiers compared to lists?

[@huynhluuvinhphong9728]

it is definately link list in C++, isn't it

[@Chillymosh]

Even though this video's intention is to show deques, it is definitely not the most efficient / optimised way to solve this problem :)

[@thelavagod]

what is your vscode theme

[@Aadoxide]

synthwave '84