Ошибка нечетного / четного нерабочего алгоритма совершенного перемешивания - PullRequest
Новая
       12

Ошибка нечетного / четного нерабочего алгоритма совершенного перемешивания

0 голосов
/ 22 февраля 2019 
private static final int SHUFFLE_COUNT = 5;


private static int[] VALUES = {1, 2, 3, 4, 5, 6};  


//broken for when  SHUFFLECOUNT and VALUES are EVEN
public static void perfectShuffle(int[] values) {
    int[] values1 = Arrays.copyOf(values, values.length);
    int k = 0; 
    for(int j = 0; j <= values.length / 2; j++) {
        values[k] = values1[j];
        k = k + 2; 
    }
    k = 1; 
    for(int j = (values.length / 2) + 1; j < values.length; j++) {
        values[k] = values1[j];
        k = k + 2; 
    }

}

public void testPerfectShuffle() {
    System.out.println("Results of " + SHUFFLE_COUNT +
                             " consecutive perfect shuffles:");
    for (int j = 1; j <= SHUFFLE_COUNT; j++) {
        perfectShuffle(VALUES);
        System.out.println("  " + j + ":" + Arrays.toString(VALUES));
    }
    System.out.println();
}

Я работаю над реализацией идеального алгоритма тасования, и по какой-то причине мой тест работает, когда число проверяемых значений нечетно, например, private static int[] VALUES = {1,2,3,4,5}; проходит , хотя, к сожалению, private static int[] VALUES = {1,2,3,4,5,6} нет.Любая помощь приветствуется!

1 Ответ

0 голосов
/ 22 февраля 2019

Помогло исправление условия цикла на «следующий больший».Он тасует и делает это для четных и нечетных массивов.Так что это работает.Определите это с помощью своего кода (независимо от размера массива: 5,7 .. первое число всегда остается на своем месте).Вывод вашего неизмененного кода с массивом нечетного размера: 

  1:[1, 4, 2, 5, 3]
  2:[1, 5, 4, 3, 2]
  3:[1, 3, 5, 2, 4]
  4:[1, 2, 3, 4, 5]
  5:[1, 4, 2, 5, 3]

Приведенный ниже код ведет себя аналогично - поскольку вопрос о создании совершенно другого алгоритма перемешивания не был в этом вопросе - не так ли?

Если я получилнеправильная логика, пожалуйста, поместите некоторую информацию о том, как именно тасование должно логически работать в вашем вопросе - в противном случае у меня нет никакого способа узнать, кроме того, что он должен тасовать все числа за исключением границ массива (может остаться), что делает приведенный ниже код,

(И я сделал testMethod статичным, чтобы я мог просто вызывать его из основного упрощенного тестирования для меня). 

public class PerfectShuffle {

    private static final int SHUFFLE_COUNT = 5;

    private static int[] VALUES = {1, 2, 3, 4, 5, 6};

//broken for when  SHUFFLECOUNT and VALUES are EVEN
    public static void perfectShuffle(int[] values) {
        int[] values1 = Arrays.copyOf(values, values.length);
        int k = 0;
        //take the next bigger int for length/2(round up) 
        for (int j = 0; j < (values.length -1) / 2 +1 ; j++) {
            values[k] = values1[j];
            k = k + 2;
        }
        k = 1;
        //take the next bigger int for length/2(round up)
        for (int j = (values.length -1)/ 2  + 1; j < values.length; j++) {
            values[k] = values1[j];
            k = k + 2;
        }

    }

    public static void testPerfectShuffle() {
        System.out.println("Results of " + SHUFFLE_COUNT
                + " consecutive perfect shuffles:");
        for (int j = 1; j <= SHUFFLE_COUNT; j++) {
            perfectShuffle(VALUES);
            System.out.println("  " + j + ":" + Arrays.toString(VALUES));
        }
        System.out.println();
    }
    public static void main(String ... args){
        testPerfectShuffle();
    }
}

Пример выполнения: 

Results of 5 consecutive perfect shuffles:
  1:[1, 4, 2, 5, 3, 6]
  2:[1, 5, 4, 3, 2, 6]
  3:[1, 3, 5, 2, 4, 6]
  4:[1, 2, 3, 4, 5, 6]
  5:[1, 4, 2, 5, 3, 6]

FWIWвход и перестановка.Предполагается, что оба корректно работают только с четными размерами массива (в зависимости от определения «правильного»), но не генерируют ошибки с нечетным: 

public static void inShuffle(int[] values) {
    int[] values1 = Arrays.copyOf(values, values.length);
    for (int j = 0; j < values.length / 2; j++) {
        values[j*2] = values1[j];
    }
    for (int j = 1; j < values.length / 2; j++) {
        values[j*2-1] = values1[(values.length / 2)+j-1];
    }
}

public static void outShuffle(int[] values) {
    int[] values1 = Arrays.copyOf(values, values.length);
    for (int j = 0; j < values.length / 2; j++) {
        values[j*2] = values1[(values.length / 2)+j];
    }
    for (int j = 0; j < values.length / 2; j++) {
        values[j*2+1] = values1[j];
    }
}
...