代码之家 › 专栏 › 技术社区 › Jon Cage

用旋转和交换对二维环形阵列进行排序

swap rotation multidimensional-array sorting algorithm

1

Jon Cage · 技术社区 · 15 年前

我试着想出一个算法,但做不到。问题是:

共有16个元素,按四种类型(a、b、c和d)分组。我们还有四组,A,B,C和D。

在初始状态下,四个组各有四个随机元素,例如:

A: c, c, a, d
B: b, b, a, a
C: b, b, c, c
D: d, d, d, a

组中元素的顺序很重要。

允许两种操作:

c, c, a, d -> d, c, c, a

2) 将一个组中的两个相邻元素与相邻组中的相应元素交换,考虑到第一个和最后一个组和元素也是相邻的,所以:

A: (c, c), a, d
B: (b, b), a, a

->

A: (b, b), a, d
B: (c, c), a, a

或

A: c), c, a, (d
D: d), d, d, (a

->

A: d), c, a, (a
D: c), d, d, (d

A: a, a, a, a 等)。该算法不一定要在时间和解决方案方面是最优的,但它应该是相当快的平均(即没有暴力)。

2 回复 | 直到 15 年前

1

4

Aryabhatta Aryabhatta 15 年前

X: b - - -
Y: - b b b

我们可以通过

循环移位X。

X: - - b - 
Y: - b b b

交换中间

X: - b b -
Y: - - b b

案例二)

X: b - b -
Y: b - b -

成功

X: - b - b
Y: b - b -

交换最后两个。

另一种情况是微不足道的。

现在给定特定字母在2、3或4行中的任何分布,我们可以确保它只出现在两行中。我将把它留给你,因为它很容易看到和难以键入!

(如果它只出现在一行中,我们的工作主要是为了那封信)

因此,算法将是

现在执行以上操作,使A成为aaaa。

考虑B,C,D。确保b只出现在两行中。使B成为上述bbbb。

忽略B。

给定C和D,你可以用上面的方法使C为cccc,D为dddd。

2

1

Griff 15 年前

我最初的想法是尝试某种形式的动态规划——这个问题似乎与 Edit Distance 因为您有一组有限的操作和一个已知的所需的结束状态。动态规划方法将产生一个多时间算法。但是,就像我说的,这正是我开始搜索算法的地方,我不知道这种方法是否真的有效。如果我晚一点再考虑的话。

希望这有帮助!