1

我正在尝试编写我的第一个算法，这是我假设要使用的伪代码。该算法假设为 k 个点置换集合 {0,1,2,3,4,5,6,7,8,9}。例如 n= 设置 0-9 所以 n=10 和 r=kn^r 排列

所以 U={0,1,2,3,4,5,6,7,8,9} （单链表）
S 最初是空的，让 k=2。该集合应该有 10^2 个排列。按照伪代码一步一步..

1）“从U中删除e”和“添加到S的末尾”

U={1,2,3,4,5,6,7,8,9}

S={0}

2) 然后它再次执行“PuzzleSolve(k-1,S,U)”，因为 k!= 1

U={2,3,4,5,6,7,8,9}

现在 S={0,1} 和 k =1，因此它检查解决方案。假设它没有找到解决方案.. 1 返回 U 并从 S 中删除。

现在：

U ={2,3,4,5,6,7,8,9,1}

S ={0}

所以这会不断重复，直到 U 中的所有数字都与 0 匹配，因为第一行中的 for 循环。但是我的问题是，如何从 S 的末尾删除 e？我想让 S 成为一个链表，但我认为不可能从单链表的末尾删除一个链接。我应该为 S 使用什么数据结构？

Algorithm PuzzleSolve(k,S,U):

Input: Integer k, sequence S, and set U (universe of elements to test)

Output: Enumeration of all k-length extensions to S using elements in U without repetitions


**for** all e in U **do**
  Remove e from U {e is now being used}
  Add e to the end of S
  **if** k = 1 **then**
         Test whether S is a configuration that solves the puzzle
         **if** S solves the puzzle **then**
           **return** “Solution found: ” S
**else**
  PuzzleSolve(k - 1, S,U)
Add e back to U {e is now unused}
Remove e from the end of S
4

3 回答 3

2

在这种情况下，使用数组或 arrayList 是有意义的。由于您已经知道集合的大小，因此无需使用链表。但是，从您的问题来看，您是否必须创建自己的结构或是否可以使用内置结构尚不清楚。如果是不能使用数组的情况，那么你可以实现一个链表。您应该使您的链表可迭代，以便您可以使用 for-each 循环对其进行迭代。

您在创建链接列表方面需要帮助吗？

于 2013-09-07T19:10:02.270 回答
1

你发布的问题有点令人困惑，因为你写的好像我们坐在你旁边读你的作业……我们不是。伪代码描述了一种递归的蛮力算法来解决问题——尝试所有可能的解决方案，直到找到一个可行的解决方案。

另一方面，您的问题是“该算法应该为 k 个点置换集合”。呃...不是根据伪代码。

通过阅读伪代码，我的理解是你从一个宇宙集开始：

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

并且您想尝试所有“没有重复的宇宙有序 k 元组”。我们的意思是：

(0, 1), (0, 2), (0, 3), ..., (0, 9)
(1, 0), (1, 2), (1, 3), ..., (1, 9)
(2, 0), (2, 1), (2, 3), ..., (2, 9)
...
(9, 0), (9, 1), (9, 2), ..., (9, 8)

这不是编写代码所必需的，但“无重复的有序 k 元组”的数量可以通过|U| * (|U| - 1) * ... * (|U| - k + 1)或在这种情况下公式化地描述：

10 * (10 - 1) => 90 (you can cross-check with the brute-force enumeration
above)

现在回答您的问题，我将只使用作为ArrayList基本 java 库的一部分的一个：http: //docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html。

如果不需要，您不想编写自己的数据结构。代码支持ArrayList很重要。除非您的教授禁止您使用它们，否则我不会尝试模仿其中的一部分。您可以使用基本数组，但抽象很好......为什么不使用它？用 an 实现该伪代码会更容易，ArrayList因为该伪代码几乎与 上的操作相同ArrayList，例如remove()and add()。

如果您编写自己的数据结构，则必须实现类似的操作……这可能是练习的一部分。如果您在执行该操作时遇到问题，请在单独的帖子中提出新问题。

于 2013-09-07T20:59:44.450 回答
0

使用数组，并使用索引：

int[] all; int u_begin, u_end, s_begin, s_end;

在哪里

u_begin=0; u_end=10-k-1; s_begin=10-k, s_end=9;

基本上，数组的开头是 U，结尾是 S，并且您使用索引来跟踪分隔的位置。我使用了 4 个索引来让您更好地理解，但实际上只需要一个，k，您可以从中计算出其他所有内容。

当您的代码需要时

Remove e from U {e is now being used}
  Add e to the end of S

更改 k 的值，将其增加 1。并通过修改索引和适当地交换元素来调整您的算法以使用数组。

于 2013-09-07T20:38:15.903 回答