CODEWITHSUNDEEP
javaalgorithm
Steven
Steven

Reputation: 55

Don't know what data structure to use for my algorithm

I'm trying to write my first algorithm and this is the pseudo code I am suppose to go off of. The algorithm is suppose to permute the set {0,1,2,3,4,5,6,7,8,9} for k spots. e.g n= set 0-9 so n=10 and r=k n^r permutations

so U={0,1,2,3,4,5,6,7,8,9} (singly linked list)
S is initially empty and let k=2. there should be 10^2 permutations of the set. following the pseudo code step by step..

1) "remove e from U" and "add to the end of S"

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

S={0}

2) it then does "PuzzleSolve(k-1,S,U)" again since k!= 1

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

S={0,1} and k =1 now, so it checks for solutions. Assuming it doesn't find a solution.. the 1 goes back to U and is removed from S.

now:

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

S ={0}

so this keeps repeating until all the numbers in U get matched up with 0 because of the for loop in the first line. However my question is, how can I remove e from the end of S? I wanted to make S a linked list but I think it is impossible to remove a link from the end of a singly linked list. What data structure should I use for 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

Upvotes: 1

Views: 607

Answers (3)

rliu
rliu

Reputation: 1148

The question you posted is a bit confusing because you wrote it as if we're sitting there next to you reading your homework... we're not. The pseudo-code describes a recursive, brute-force algorithm to solve a problem--try all possible solutions until we find one that works.

On the other hand, your question asks "the algorithm is supposed to permute the set for k spots". Er... not according to the pseudo-code.

From reading the pseudo-code, my understanding is that you start with a universe set:

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

And you want to try all "ordered k-tuples of the universe with no repeats". By that we mean:

(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)

This isn't necessary to write your code, but the number of "ordered k-tuples without repeats" can be described formulaically by |U| * (|U| - 1) * ... * (|U| - k + 1) or in this case:

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

Now to answer your question, I would just use an ArrayList which is part of the base java libaries: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html.

You don't want to code your own data structure if you don't need to. The code backing ArrayList is non-trivial. I wouldn't try to emulate even parts of it unless your professor forbade you from using them. You can use a basic array, but abstraction is nice... why not use it? It'll be easier to implement that pseudo-code with an ArrayList because that pseudo-code translates almost identically to operations on ArrayList, such as remove() and add().

If you wrote your own data structure you'd have to implement similar operations... which could be part of the exercise. If you are having trouble with that implementation, ask a new question in a separate post.

Upvotes: 1

azzurroverde
azzurroverde

Reputation: 577

Use an array, and use indexes:

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

where

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

Basically, the beginning of the array is U, the end is S, and you use an index to keep track of where the separation is. I used 4 indexes to make you understand better, but actually only one is required, k, and you can calculate everything else from that.

When your code requires

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

Change the value of k, increasing it by 1. And adapt your algorithm to use the array by modifying the index and by swapping elements appropriately.

Upvotes: 0

Arash Saidi
Arash Saidi

Reputation: 2238

In this case it would make sense to either use an array or arrayList. Since you already know the size of the set there is no need to use linked list. However, from your question it is not clear whether you must create your own structure or if you can use built-in structures. If it is the case that you cannot use an array, then you could implement a linked list. You should make your linked list iterable so that you can iterate through it with a for-each-loop.

Do you need help with creating a linked list?

Upvotes: 2

Related Questions