1

シャッフルアルゴリズムに疑似コードを使用して、それを動作するJavaコードに変えるのに非常に苦労しています。リンクされたリストをシャッフルしようとしています。全体として、メソッドはリンクされたリストの先頭のポインターを受け取り、同じリストの先頭へのポインターをランダムに返します。作成した getLength および getItem メソッドを使用したい。

public static ListElement shuffle(ListElement head){
  head = head.getLength();
  ListElement head2= null;
  while( head == null) {
    int random = (int) Math.random() *  n;
    for(int i=0;i<random;i++){
        head= head.getNext();
    }
  }
  return head;    
}

擬似コード:

A list L of length n
A new list R, empty
while L is not empty
   pick a random k 
   such that 0<=k<= (length L)
   remove the kth element of L
      call it e
   prepend e to R
4

3 に答える 3

0

疑似コードの問題は、最悪のシナリオでは、要素を削除して新しいリストに追加するたびに、元のリストの最後まで反復する必要があることです。

元のリスト o = [a,b,c,d,e,f,g]
新しいリスト: n = []

o = [a、b、c、d、e、f]
n = [g]

o = [a、b、c、d、e]
n = [g、f]

o = [a,b,c,d]
n = [g,f,e]

...

私が今考えることができる最も効果的な答えは、リストのサイズの配列を作成し、元のリンクされたリストを反復処理して、ランダムな場所で配列に要素を挿入することです:

元のリスト o = [a,b,c,d,e,f,g]
新しい配列 a = [,,,,,,]

o = [b,c,d,e,f,g]
a = [,,a,,,,]

o = [c,d,e,f,g]
a = [,,a,,b,,]

o = [d,e,f,g]
a = [c,,a,,b,,]

o = [e,f,g]
a = [c,,a,,b,d,]

...

それらを配列に入れたら、配列をループしてリンクを修正します。

getNext()オリジナルでは、 6 回、次に 5 回、次に 4 回、次に 3 回呼び出す必要がありました...

私の場合、getNext()6回呼び出してから、配列をループして「次の」参照をリセットします。

于 2012-07-12T00:14:13.827 に答える
0 
head = head.getLength();

そうあるべきかのように見えるint n = head.getLength();

while( head == null) {

そうあるべきかのように見えるwhile (head != null) {

int random = (int) Math.random() *  n;
for(int i=0;i<random;i++){
    head= head.getNext();

head 変数を上書きしています。リストの k 番目の要素を見つけるには新しい変数を使用する必要があり、head は古いリストを指しているままにします。

要素を見つけたら、まだ何もする必要はありません。古いリストから抽出し (ハード)、新しいリストの先頭に追加する必要があります。

return head;

新しいリストを返す必要があります。

于 2012-07-12T00:06:48.830 に答える
0

擬似コードに従うように、コードを少し書き直しただけです。

ListElement head2 = null;
int length = head.getLength();

while (head != null) {
    int k = (int) Math.random() * length;

    // Assume there is function deleteAt(index) that removes
    // the element at specified index and returns the deleted
    // element
    ListElement e = head.deleteAt(k);
    // Although I can just give the implementation - I'll leave this
    // as exercise.

    // You can have a function that add element to front
    // head2.addFront(e);
    e.setNext(head2);
    head2 = e;

    // Instead of querying the length again
    // decrement the length
    length--;
}
return head;
于 2012-07-12T00:08:59.430 に答える