HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Algorithm to compose identity from a set of permutations

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
identityalgorithmcomposefromsetpermutations

Problem

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity permutation?

Solution

Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.

Context

StackExchange Computer Science Q#43084, answer score: 4

Revisions (0)

No revisions yet.