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

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

swap rotation multidimensional-array sorting algorithm

Jon Cage · 技术社区 · 16 年前

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

共有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 回复 | 直到 16 年前

Aryabhatta Aryabhatta 16 年前

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。

Griff 16 年前

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

希望这有帮助!

推荐文章

Paul Williams · 迭代数组时输出有问题

1 年前

pasty guacamole · 在结构体(C)中使用双指针访问2d数组上的信息

2 年前

Muffinman · 使用Excel O365,如何在两列上使用唯一性,对相关数据进行排序和复制?

2 年前

Suyash Nachankar · 为什么矩阵的所有行都与最后一行相同?

2 年前

Vyacheslav Verkhovin · C中二维数组的Typedef和指针上的访问

2 年前

Aditi · 我正在尝试用Java解决一个数字模式问题。我已经写了代码,如果有人能对我现有的sol进行更改,我将不胜感激

2 年前

neo · 为什么我不能访问以取消引用int指针作为索引的char指针数组中的位置

2 年前

Omprakash · 使用Google工作表中的多行和多列进行筛选

2 年前

Genki · Bash:如何从多维数组中的命名键获取值

2 年前

Insert0Name0Here · 将多维数组中的数组传递给C中的函数#

2 年前