[Pattern] Permutations

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

dheetCoder's blog

[Pattern] Permutations

By dheetCoder, history, 20 months ago, In English

Suppose we have given a permutation of length n. Can we find the count of a specific binary string of length n-1. Such that for each permutation p we increment the count of binary string b, where b[i]=='1' if p[i+1]>p[i] else '0' for each i from 0...n-2. For n=5 I have runned the bruteforce code

Code

        int n=5;
        vector<int>v(n);
        for(int i=0;i<n;i++){
            v[i]=i+1;
        }
        map<string,int>mp;
        for(int i=0;i<120;i++){
            string str;
            for(int i=0;i<4;i++){
                if(v[i+1]>v[i]){
                    str+=('1');
                }else{
                    str+=('0');
                }
            }
            next_permutation(all(v));
            mp[str]++;
        }
        for(auto [x,y]: mp){
            cout<<x<<' '<<y<<"\n";
        }

Getting the output

result

Some pattern we can observe. But can we predict the actual number of these string ??

pattern recognition, next_permutation

dheetCoder
20 months ago
3

Comments (2)

Show archived | Write comment?

TheScrasse

20 months ago, # |

Yes, but it's hard.
1776N - Count Permutations

→ Reply

TheScrasse

20 months ago, # ^ |

Actually the solution in $$$O(n^2)$$$ is much easier. See this problem.

Solution sketch

→ Reply