Is there a theorem that a set of binary swaps can affect any permutation?

  • I
  • Thread starter swampwiz
  • Start date
  • #1
swampwiz
486
44
Is there a theorem that states that a set of binary swaps can result in any permutation?

For example, the original set (1,2,3,4,5) can have the swap (24) and result in (1,4,3,2,5). is there a set of specific swaps for each net result permutation?
 

Answers and Replies

  • #3
swampwiz
486
44
I was just thinking. Since the quicksort algorithm only does binary swaps, and can sort any initial permutation order - and thus could be run in reverse to get to any permutation from the sorted set - doesn't this also prove this theorem?
 
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
5,474
1,414
I guess the question is how do you prove quicksort actually sorts the list at the end? I think you need this theorem to prove it, or at least to substantially prove this theorem as part of your proof of the algorithms correctness
.
 
  • #5
swampwiz
486
44
I wonder if anyone has done a YouTube video that does this proof without requiring a lot of abstract algebra terminology.
 
  • #6
swampwiz
486
44
OK, I think I've got this. Given a vector of indices, a binary swap can be accomplished by concatenating it with an elementary swap matrix. Since the Gauss-Jordan reduction algorithm can decompose any matrix into a set of elementary matrices, and a permutation matrix is composed only of such elementary swap matrices, and as well because the determinant of an elementary swap matrix is -1, its inverse exists. Thus, the identity matrix can have a set of concatenations of swap matrices to get to any possible permutation.
 
  • #7
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
29,610
15,079
Is there a theorem that states that a set of binary swaps can result in any permutation?
Yes, there is such a theorem. This is worded as: "The symmetric group is generated by transpositions"

Note that this overdoes it - it proves that a set of adjacent binary swaps can result in any permutation.
 
  • Like
Likes swampwiz, sysprog and member 587159
  • #8
Infrared
Science Advisor
Gold Member
988
550
This fact is much easier than it seems like you think it is. If I have the numbers 1,...,n in some order and I want to rearrange them into the standard order, then I first make a transposition to put ##1## in the first spot and leave it alone thereafter. Then I make a transposition to put ##2## into the second spot, etc.
 
  • #9
swampwiz
486
44
This fact is much easier than it seems like you think it is. If I have the numbers 1,...,n in some order and I want to rearrange them into the standard order, then I first make a transposition to put ##1## in the first spot and leave it alone thereafter. Then I make a transposition to put ##2## into the second spot, etc.
Yes, that is the idea I was getting at in a subsequent post.
 

Suggested for: Is there a theorem that a set of binary swaps can affect any permutation?

Replies
19
Views
2K
Replies
21
Views
592
  • Last Post
Replies
23
Views
2K
Replies
5
Views
414
Replies
1
Views
578
Replies
34
Views
1K
  • Last Post
Replies
6
Views
641
Top