nor's blog

[Tutorial] A comprehensive guide to permutations for beginners
By nor, 23 months ago, In English

https://nor-blog.codeberg.page/posts/2023-01-09-permutations-for-beginners/

  • Vote: I like it
  • +414
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +50 Vote: I do not like it

cool blog better than the previous one

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nor speedrunning top of contributions haha :) Great post (like the others)

→ Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

man just keep bringing these tutorials man you are the best tutorial writer we have plus you always bring something relevant and new to learn.Much love.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope someone overtakes you in the top 10 contributors so that we keep getting norz blogs.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

many people have created blogs on dp buts your blogs are just so special why don't you make a blog on dp covering all advance aspects of dp with some good problems attached to that blog that will be helpful in learning intermediate and advance dp

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    DP as a topic is huge, and it's impossible to cover even half of it (or at least half of what I know about it) in a single blog. I might write something on DP in the distant future, but no promises. I'd recommend learning recursion, reading other tutorials on DP, and solving problems from CSES and AtCoder DP contest.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the next premutation section

"Note that the smallest number in this sequence that is larger than a_i will be the new element at position i."

is it a_i or a_(i-1) ?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In find kth-next functional graphs,

"Each weakly connected component consists of two parts: a directed cycle and directed trees rooted at distinct vertices in the cycle, directed towards the root (also called reverse-oriented arborescences)."

How come directed trees are also present ? Took example from planet queries I

[2,1,1,4]
cycle for each i
1->2->1
2->1->2
3->1->2->1
4->4
I couldn't find any directed tree here.

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hello nor ,

Thank you very much for such a great Blog.

I had problem understanding in the case of counting derangements using recursion...

Our recurse() (in original example it is mentioned as method D()) method takes 'N' as input where we have 'N' empty places fill. We also make sure that all the 'N' has one-to-one mapping with the places ( such that there exist one 'i' for which a[i] == i ).

when a[n] = k != n and a[k]=n , the problem reduces to recurse(n-2), this part is clear. After we make place 'n' on 'k's places and 'k' on 'n's place, rest of the n-2 numbers are still having one-to-one mapping with remaining places to fill.

But in the case of a[k] != n , we have n-1 places to fill and n-1 numbers , but we don't have one-to-one mapping between them. How can we use same recurse() method on remaining n-1 places ?

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Hello nor I am elaborating further on my doubt,

    if we have N=6, and for example we are putting value '3' on the index '6' and trying to count number of derangements for remaining values, (we could pick any value other than '6')

    Remaining values = { 1 , 2 , 4 , 5 , 6 } Remaining Indices = { 1 , 2 , 3 , 4 , 5 } ( 6'th index is taken by value '3' ) .

    Now, when we put value '6' anywhere in remaining indices. There are two cases, 1) We place value 6 on index 3. 2) We don't place value 6 on index 3.

    CASE 1 If we place value 6 on index 3 , then... remaining values = { 1 , 2 , 4 , 5 } remaining indices = { 1 , 2 , 4 , 5 } So, our recurrence is still good to go,,, we can continue with our recurrence.

    CASE 2 If we place value 6 on any index other than 3, we have (n-2) such a way to do it, but for example I am just taking randomly index 2, remaining values = { 1 , 2 , 4 , 5 } remaining indices = { 1 , 3 , 4 , 5 }

    How can we call our recurrence now ??? there is no one-to-one mapping between remaining values and remaining indices... Please someone help me understand this.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you, very useful.

→ Reply