\begingroup

给定数组AAA （A0，A1，… ，​​An）（A0，A1，。。。，An）(a_0, a_1,… , a_n) 作为（0，1 ，… ，n ）​​​​（0，1，。。。，n）(0, 1,…,n)在哪里n≥2​​n≥2n ≥ 2. 排序数组AAA进入数组（0，1 ，… ，n​​​​（0，1，。。。，n(0, 1,…,n） 和222注意事项：

  • 111交换非零值时计算 swap，并且000在数组中AAA。这是唯一允许的交换方式。
  • 尽可能少地交换。

数组将永远处于混乱状态。

示例 I/O

仅打印111如果存在多个同样最优的解决方案，则输出。


输入和输出格式灵活。

Input:
2 3 0 1 5 4
Output:
2 3 1 3 4 5 4

可视化

Original A array: 2 3 0 1 5 4
1. (2): 0 3 2 1 5 4 #Swapped 2 and 0
2. (3): 3 0 2 1 5 4 #Swapped 3 and 0
3. (1): 3 1 2 0 5 4 #Swapped 1 and 0
4. (3): 0 1 2 3 5 4 #Swapped 3 and 0
5. (4): 4 1 2 3 5 0 #Swapped 4 and 0
6. (5): 4 1 2 3 0 5 #Swapped 5 and 0
7. (4): 0 1 2 3 4 5 #Swapped 4 and 0
#Swapping 7 times was the fewest swaps possible.

获胜标准

这是一个code-golf挑战。源代码字节数最少的一方获胜。

\endgroup

2

  • \begingroup
    我们可以使用1而不是0作为我们的最小输入值吗？
    \endgroup


    – 

  • \begingroup
    @JonathanAllan 任何数字作为最小输入都可以。
    \endgroup


    – 


8 个回答
8

\begingroup

，55 字节

##~##&~#&@@@D@@PermutationCycles@Ordering@#/. 1->Set@$&

输入和输出 1 索引。

                                 Ordering@#             invert permutation
               PermutationCycles@                       convert to cycles
            D@@                                          as list of lists
##~##&~#&@@@                                            convert to 1-swaps
                                           /. 1->Set@$  remove 1s

\endgroup

\begingroup

，59 字节

x=>x.map(e=(c,u)=>u-c&&u-(q=x[u&&print(u),u])&&e(x[u]=u,q))

假设第一步将 0 移到最前面是最佳的

来自 Shaggy 的 -2 个字节以及来自 Arnauld 的 -7 个字节

\endgroup

4

  • \begingroup
    例如这似乎不正确[1,2,0]
    \endgroup


    – 

  • \begingroup
    @att 反转顺序没问题。已修复
    \endgroup


    – 

  • \begingroup

    \endgroup


    – 

  • \begingroup
    （来自@Shaggy’s）
    \endgroup


    – 

\begingroup

，25字节

Ｗ∨⌕θ⁰⌊Φθ⁻κλ«ＵＭθ∧⁻κι∨κι⟦Ｉι

链接为代码的详细版本。说明：

Ｗ∨⌕θ⁰⌊Φθ⁻κλ«

虽然可以找到一个可以交换0的数字，但最好是现在所属的数字0，…

ＵＭθ∧⁻κι∨κι

…交换0该数字，然后…

⟦Ｉι

0…输出交换的数字。

\endgroup

\begingroup

，20 19

[ÐÅΔNÊ}D(#s0k+=0‚‡

在分隔的行上输出结果。

或。

解释：

（05AB1E 使用基于 0 的索引。）

[           # Start an infinite loop:
 Ð          #  Triplicate the current list
            #  (which will be the implicit input-list in the first iteration)
  ÅΔ        #  Pop one, and push the first index that's truthy for
            #  (or -1 if none are truthy):
            #   (implicitly push the current item of the list)
    NÊ      #   Check whether it's NOT equal to its index
   }D       #  Duplicate this first unsorted index
     (      #  Pop, and if it's -1 (aka the list is already sorted):
      #     #   Stop the infinite loop
  s         #  Swap so the current list is at the top again
   0k       #  Pop and get the index of the 0
     +      # †Add it to the found index
      =     #  Print it with trailing newline (without popping)
      0‚    #  Pair it with 0
        ‡  #  Swap those two values in the list:
        Â   #   Bifurcate; short for Duplicate & Reverse copy
         ‡  #   Transliterate

†这里+充当‚à（配对并保留最大值）的作用，因为列表中的第一个值未排序，在这种情况下ÅΔNÊ}会导致第一个索引为 0，并0k导致我们想要交换的索引，或者第一个值是 0，在这种情况下ÅΔNÊ}会导致我们想要交换的索引并0k导致 0。无论哪种情况，两者中有一个是 0，所以+在这里使用可以节省一个字节。

\endgroup

\begingroup

， 147   146  144 字节

q 通过在内部循环外部 分配，减少 1 个字节并提高性能while 。
通过使用元组解包分配，减少 2 个字节 o 。

A=eval(input())
B=x=1
while B!=sorted(A):
 B,y,q,*o=A[:],x,len(A)
 while y:c=B.index(0);B[B.index(z:=y%q)]=0;B[c]=z;y//=q;o=[z]+o
 x+=1
print(o)

输入和输出作为 Python 列表。

\endgroup

\begingroup

，111 字节

def f(a):x=a.index;z=x(0);a[x(i:=z or next(j for j in a if x(j)-j))]=0;a[z]=i;return[i][a>sorted(a):]or[i]+f(a)

\endgroup

\begingroup

，94 91 80 字节

f=\(a){i=max(j<-which(a<2),a[a>seq(a)]*(j<2))
a[a==i]=1
a[j]=i
if(i>1)c(i,f(a))}

基于 1 的输入和输出索引。

是打印出交换的每个阶段的版本的链接，中编造的各种测试用例的链接。

Ungolfed，原始

zeroswapsort=
f=function(a            # recursive function with argument
                        # a = array to sort
            ,j=1){      # set j = 1 
if(i<-which(!a)-1)      # if zero is not in the first position
                        #   set i = (zero-based) position of zero
                        #    (this is the number to swap)
                  j=i+1 #   set j = (one-based) index to swap
else                    # otherwise, leave j as position of zero = 1
     i=max(0,a[a>seq(a)-1])
                        #   and set i = 0 (if array is sorted)
                        #   or i = any value in the wrong position
                        #   (chosen as maximum difference to the sorted array)
a[a==i]=0               # now, do the swap
a[j]=i 
if(i)                   # and if the array wasn't already sorted
     c(i                # return the swapped value
        ,f(a))}         # and recursively sort the swapped array

\endgroup

\begingroup

，15字节

* 等待确认是否可以接受（发布是因为其他两个人已经认为可以接受）。

nJ,i€1ṄḊ¡€ṚƬyµƬ

一个单子 Link，接受基于 1 的值列表并将要交换的每个值打印到1标准输出。请注意，这还会产生一个列表列表，调用者可能会忽略这些列表（这是状态加上一个额外的伪状态）。

* 如果我们必须使用基于 0 的方法来处理当前的问题，那么不同的方法可能比调整这种方法更简洁。

（页脚丢弃产生的列表列表）。

如何？

nJ,i€1ṄḊ¡€ṚƬyµƬ - Link: list, P, of values [1..len(P)]
             µƬ - collect up while distinct, applying:
 J              -   indices -> [1..len(Current)] (==[1..len(P)])
n               -   {Current) not equal {that} (vectorises)
  ,             -   pair {that} with {Current}
   i€1          -   index of 1 in each of those -> ValuesToSwap
         €      -   for each:
        ¡       -     if...
       Ḋ        -     ...condition: dequeue -> truthy if ValueToSwap > 1
      Ṅ         -     ...then: print it
           Ƭ    -   collect up while distinct, applying:
          Ṛ     -     reverse
            y   -   translate {Current} using {that} -> swap the Values

\endgroup