VPF::shuffle - Форум программистов

dorogoyIV

Дата 23.7.2007, 13:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: нет
Всего: 46

в J2ME я не нашел метода shuffle(), который есть в SE. Random не подходит, потому, что нужно перемешать некоторый диапазон значений, что бы они не повторялись.
как это делается?
неужели применять Random и проверять - было значение или нет? smile

math64

Дата 23.7.2007, 14:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Нужно брать исходники shuffle() из SE и переписывать их для ME

Код


Random rnd = new Random();
void shuffle(Object[] arr) {
  for (int i=size; i>1; i--)
    swap(arr, i-1, nextInt(i));
  }
}
void swap(Object[] arr, int i, int j) {
  Object o = arr[i];
  arr[i] = arr[j];
  arr[j] = o;
}
int nextInt (int i) {
  // В CLDC 1.0 нет rnd.nextInt(i)
  return (int)((((long)rnd.nextInt()&0xFFFFFFFF)*i)>>32);
}

nagliyvred

Дата 23.7.2007, 15:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 54
Регистрация: 2.10.2005

Репутация: 3
Всего: 3

Я не совсем понял что не должно повторяться - индексы переставляемых элементов? Ну так пройдитесь по всей коллекции линейно. Именно так собсно метод shuffle() в SE и реализован:

Код


/**
     * Randomly permute the specified list using the specified source of
     * randomness.  All permutations occur with equal likelihood
     * assuming that the source of randomness is fair.<p>
     *
     * This implementation traverses the list backwards, from the last element
     * up to the second, repeatedly swapping a randomly selected element into
     * the "current position".  Elements are randomly selected from the
     * portion of the list that runs from the first element to the current
     * position, inclusive.<p>
     *
     * This method runs in linear time.  If the specified list does not
     * implement the {@link RandomAccess} interface and is large, this
     * implementation dumps the specified list into an array before shuffling
     * it, and dumps the shuffled array back into the list.  This avoids the
     * quadratic behavior that would result from shuffling a "sequential
     * access" list in place.
     *
     * @param  list the list to be shuffled.
     * @param  rnd the source of randomness to use to shuffle the list.
     * @throws UnsupportedOperationException if the specified list or its
     *         list-iterator does not support the <tt>set</tt> operation.
     */
    public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

dorogoyIV

Дата 23.7.2007, 16:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: нет
Всего: 46

Цитата

Я не совсем понял что не должно повторяться - индексы переставляемых элементов?

например:

Код


List list=new ArrayList(); // это тоже для SE
list.add(1);
list.add(2);
list.add(3);
// перемешиваем, что бы 1,2 и 3 не повторялись
// в SE можно так:
// Collections.shuffle(list);
// в МЕ так сразу не сделаешь

буду пробовать код math64

Это сообщение отредактировал(а) dorogoyIV - 23.7.2007, 16:07

math64

Дата 24.7.2007, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Код


/** Получить массив перетасованных целых чисел от 1 до n. */
int[] shuffle(int n) {
  int[] arr = new int[n];
  for (int i = size; i > 0; i--) {
    arr[i - 1] = i;
  }
  for (int i=size; i>1; i--) {
    int j = nextInt(i);
    int tmp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = tmp;
  }
}

Это сообщение отредактировал(а) math64 - 24.7.2007, 13:52

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java ME (J2ME) \| Следующая тема »