给定数组AAA (A0,A1,… ,An)(A0,A1,。。。,An)(a_0, a_1,… , a_n) 作为(0,1 ,… ,n )(0,1,。。。,n)(0, 1,…,n)在哪里n≥2n≥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
8 个回答
8
,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
|
,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
–
|
,25字节
W∨⌕θ⁰⌊Φθ⁻κλ«UMθ∧⁻κι∨κι⟦Iι
链接为代码的详细版本。说明:
W∨⌕θ⁰⌊Φθ⁻κλ«
虽然可以找到一个可以交换0
的数字,但最好是现在所属的数字0
,…
UMθ∧⁻κι∨κι
…交换0
该数字,然后…
⟦Iι
0
…输出交换的数字。
\endgroup
|
,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
|
, 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
|
,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
|
,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
|
,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
|
我们可以使用
1
而不是0
作为我们的最小输入值吗?\endgroup
–
@JonathanAllan 任何数字作为最小输入都可以。
\endgroup
–
|