[Pattern] Permutations

→ Pay attention

Before contest
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

dheetCoder's blog

[Pattern] Permutations

By dheetCoder, history, 13 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
13 months ago
3

Comments (2)

Show archived | Write comment?

TheScrasse

13 months ago, # |

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

→ Reply

TheScrasse

13 months ago, # ^ |

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

Solution sketch

→ Reply