2
$\begingroup$

For a given binary array like {0, 1, 1, 0,..}, I need to find the shortest permutation, sorting it in standard order {0,0,...,1,1,..}.
There is a warning in documentations for FindPermutation:

For expressions containing repeated parts, the permutation is not uniquely defined

And it's easily to find the next example:

  data = {1, 1, 0};
  FindPermutation[data, Sort@data]
  (*Don't confuse it with FindPermutation@data,
  it's not the same!*)
 Output: Cycles[{{1, 2, 3}}]
(*Also:*)
PermutationCycles@Ordering@data
Output: Cycles[{{1, 3, 2}}]

But:

 Permute[data, Cycles[{{1, 3}}]]
    Output: {0, 1, 1}

So FindPermutation produces not shortest result. And how to find shortest not manually?
Is it possible to find all that produce the same result?

$\endgroup$
5
  • $\begingroup$ @bmf Edit post, I mean warnings in the docs $\endgroup$
    – lesobrod
    Jan 4 at 16:14
  • $\begingroup$ Maybe Ordering will help? $\endgroup$ Jan 4 at 16:26
  • $\begingroup$ @DanielLichtblau, yes I tried PermutationCycles@Ordering@arr, but does this guarantee shortest result? $\endgroup$
    – lesobrod
    Jan 4 at 16:31
  • $\begingroup$ Please keep it civil, people. We're all friends here and it happens that someone misinterprets the meaning. $\endgroup$
    – halirutan
    Jan 4 at 22:50
  • $\begingroup$ I believe Ordering is "stable" in the sense that equal elements won't get swapped. So it should give a minimal permutation (he said). $\endgroup$ Jan 4 at 23:33

1 Answer 1

1
$\begingroup$

The only direct method that I've found is (without useless FindPermutation) :

data = {0, 1, 1, 1, 0, 0};
perms = Permutations@Range@Length@data;
res = MinimalBy[Select[perms, data[[#]] == Sort@data &], 
  PermutationOrder]

Output: {{1, 5, 6, 4, 2, 3}, {1, 6, 5, 4, 3, 2}}

This code guarantees shortest length of permutations that produce sorted data.
Shorter and smarter result is very welcome!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.