Распечатать определенное количество перестановок (Java) - PullRequest
Новая
       10

Распечатать определенное количество перестановок (Java)

0 голосов
/ 02 ноября 2018

Код, который я написал, принимает элементы массива и проходит через массив, чтобы получить все перестановки. Но мне нужно, чтобы отображалось только определенное количество перестановок:

Окончательный код должен дать только 6 перестановок из 9 элементов (иными словами, выведите первые 60480 схем из общего количества 362880 выходов). Для простоты я работаю с 4-мя элементами в массиве, и я распечатываю все 24 аранжировки. Но мне нужен код для работы с любым количеством перестановок. Например, если мне нужно распечатать 1-перестановку, код должен распечатать первые 4 схемы - ABCD, ABDC, ACBD и ACDB. Я не уверен, как решить это. 

public static void main(String[] args) {
    // TODO Auto-generated method stub


    String[] myArray = {"A","B","C", "D"};
    int size = myArray.length; 
    permutation(myArray, 0, size-1);

    // Calculate Permutations
    int n=size;
    int r=6; // subject to change
    int p = n - r;
    int total=1;
    int total2=1;
    int total3=0;

    for (int top=n; top>0; top--)
    {
        total *= top;
    }

    if ((n-r<0))
    {
     System.out.println("r value cannot be greater than array size");
     total3=0;
    }
    else 
    {
        for (int bot=1; bot<=p; bot++)
        {
            if (p==0) // should be -- else if (p==0) -- after correction
            {
                total2=1;
            }
            else
            {
                total2 *= bot;
            }
        }
        total3 = total/total2;
    }

    System.out.printf("%d permutations of %d elements = %d\n",r,n,total3);
    // end calculation

}
// end main

// print array
public static void prtArray(String[] myArray, int size)
{
    for(int i=0; i<size; i++)
    {
        System.out.printf("%s", myArray[i]);
    }
    System.out.println();
}

// swap elements    
public static void swap(String[] myArray, int i, int j) {
    String temp;
    temp = myArray[i];
    myArray[i]=myArray[j];
    myArray[j]=temp;
}

// permutation 
private static void permutation(String[] myArray, int b, int e)
{
    if (b == e)
        prtArray(myArray, e+1); // accounts for array of size 1
    else
    {
        for(int i = b; i <= e; i++)
        {

            swap(myArray, i, b);
            permutation(myArray, b+1, e);
            swap(myArray, i, b);

        }
    }
}
}

Ответы [ 3 ]

0 голосов
/ 02 ноября 2018

Вот полное решение для трех из пяти элементов: 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.util.stream.Collectors.toList;

public class Permutations {

  public static void main(String[] args) {
    String[] myArray = {"A", "B", "C", "D", "E"};
    List<String> list = Arrays.asList(myArray);

    List<List<String>> perms = makePerms(list, 3);
    perms.forEach(Permutations::printPerm);
    System.out.println("Size = " + perms.size());
}

  private static List<List<String>> makePerms(List<String> list, int count) {
    if (count == 1) {
      return list.stream().map(Arrays::asList).collect(toList());
    }
    return list.stream()
          .flatMap(e -> makePerms(remove(list, e), count - 1).stream()
                .map(l -> add(l, e)))
          .collect(toList());
  }

  private static <T> List<T> remove(List<T> list, T elem) {
    List<T> newList = new ArrayList<>(list);
    newList.remove(elem);
    return newList;
  }

  private static <T> List<T> add(List<T> list, T elem) {
    List<T> newList = new ArrayList<>(list);
    newList.add(elem);
    return newList;
  }

  private static void printPerm(List<String> perm) {
    perm.forEach(System.out::print);
    System.out.println();
  }
}
0 голосов
/ 03 ноября 2018

мой очень похож на донат. взять элемент и вернуть len-1 перестановки остальных элементов. 

public class Permuter {

public static void main(String[] args) {
    List<String> source = asList("A", "B", "C", "D");
    List<String> permutations = returnPermutations(source, 3, 0);
    permutations.forEach(s -> System.out.println(s));
}

private static List<String> returnPermutations(List<String> source, int choose, int len) {
    List<String> result = new ArrayList<>();

    if (len + 1 == choose) {
        return source;
    } else {
        for (String s : source) {
            List<String> tail = new ArrayList<>(source);
            tail.remove(s);
            result.addAll(returnPermutations(tail, choose, len+1).stream().map(ts -> s + ts)
                    .collect(Collectors.toList()));
        }
        return result;
    }
}

}
0 голосов
/ 02 ноября 2018

Проблема с вашим свопом. Ваш обмен не меняет местами элементы в массиве. Так как он получает две строки и меняет их местами, но не меняет значение внутри массива. Исправьте свой своп, и все будет хорошо.

...