CODEWITHSUNDEEP
pythonalgorithmperformancesortingpermutation
Carlson Bimbuh
Carlson Bimbuh

Reputation: 126

Number of sorted elements (permutations), in all possible permutations of a list

Given an array, say, arr = [5, 5, 4, 4, 2, 1], how can I find, of all possible permutations of this array, the number of permutations which are same like the original array itself (assuming the original array is always sorted in descending order). In this sample case, there will be 4 permutations equal to the original array. Well that's what I get using itertools.permutations in python. Anyone with something faster? I will be most grateful. Following is my so slow python code.

from itertools import permutations

arr = sorted(map(int, (raw_input().split())), reverse = True)

perms = permutations(n,len(arr))

cnt = 0;

for i in perms:
    if list(i) == arr: print i; cnt += 1
print cnt

Upvotes: 3

Views: 371

Answers (3)

Cid
Cid

Reputation: 15257

For N elements, the number of possible permutation is N!

If you have in example [5, 5, 5, 4, 1], there is 3! permutations where the array is the same.

I'd loop the array and store in a associated array the value and the number of that value was met.

Pseudo-code :

firstArray = [5, 5, 4, 4, 2, 1]
doubleArray = []

for each item in firstArray:
    if item is in doubleArray keys:
        doubleArray[item]++
    else:
        doubleArray[item] = 1

result = 1
for each elem in doubleArray:
    result *= fact(elem)

print "There is " + elem + " permutations possible where the original array remains the same"

Upvotes: 0

blhsing
blhsing

Reputation: 107134

You can get the product of the factorials of the lengths of all same-value subsequences:

from itertools import groupby
from functools import reduce
from math import factorial
from operator import mul
print(reduce(mul, map(lambda t: factorial(sum(1 for i in t[1])), groupby(arr))))

This outputs: 4

Upvotes: 0

Dave
Dave

Reputation: 9085

Say your array is size n and the repetitions are r1, r2, ..., rk, so that sum(ri) = n. Then the answer is the product of the factorials of the repetitions.

e.g., for arr = [5, 5, 4, 4, 2, 1], we get r = [2, 2, 1, 1], and an answer of 2! * 2! * 1! * 1! = 4

Upvotes: 4

Related Questions