1. Используйте метод двоичного состояния для поиска перестановок и комбинаций. Этот метод относительно прост для понимания, но эффективность его работы невысока. Можно использовать небольшие перестановки и комбинации данных.
Скопируйте код кода следующим образом:
импортировать java.util.Arrays;
//Используем двоичный алгоритм для полной расстановки
//счет1:170187
//счет2:291656
тест публичного класса {
public static void main(String[] args) {
длинный старт = System.currentTimeMillis();
счет2();
длинный конец = System.currentTimeMillis();
System.out.println(конец-начало);
}
частный статический void count2(){
int[] num=new int []{1,2,3,4,5,6,7,8,9};
for(int i=1;i<Math.pow(9, 9);i++){
String str=Integer.toString(i,9);
int sz=str.length();
for(int j=0;j<9-sz;j++){
стр="0"+стр;
}
char[] temp=str.toCharArray();
Arrays.sort(temp);
String gl = новая строка (темп);
if(!gl.equals("012345678")){
продолжать;
}
Строковый результат="";
for(int m=0;m<str.length();m++){
result+=num[Integer.parseInt(str.charAt(m)+"")];
}
System.out.println(результат);
}
}
публичная статическая недействительность count1(){
int[] num=new int []{1,2,3,4,5,6,7,8,9};
int[] ss=new int []{0,1,2,3,4,5,6,7,8};
int[] temp=new int[9];
в то время как (темп [0] <9) {
темп[temp.length-1]++;
for(int i=temp.length-1;i>0;i--){
если(темп[i]==9){
температура [я] = 0;
темп[я-1]++;
}
}
int []tt=temp.clone();
Массивы.сортировать(тт);
if(!Arrays.equals(tt,ss)){
продолжать;
}
Строковый результат="";
for(int i=0;i<num.length;i++){
результат+=число[temp[i]];
}
System.out.println(результат);
}
}
}
2. Используйте рекурсивное мышление для поиска перестановок и комбинаций, что требует большого объема кода.
Скопируйте код кода следующим образом:
пакетная практика;
импортировать java.util.ArrayList;
импортировать java.util.List;
общественный класс Test1 {
/**
* @param аргументы
*/
public static void main(String[] args) {
// TODO Автоматически сгенерированная заглушка метода
Объект[] tmp={1,2,3,4,5,6};
// ArrayList<Object[]> rs=RandomC(tmp);
ArrayList<Object[]> rs=cmn(tmp,3);
for(int i=0;i<rs.size();i++)
{
// System.out.print(i+"=");
for(int j=0;j<rs.get(i).length;j++)
{
System.out.print(rs.get(i)[j]+",");
}
Система.out.println();
}
}
// Находим любую комбинацию массива
статический ArrayList<Object[]> RandomC (источник Object[])
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
если (источник.длина == 1)
{
результат.добавить(источник);
}
еще
{
Object[] psource=новый объект[source.length-1];
for(int i=0;i<psource.length;i++)
{
psource[i]=источник[i];
}
результат = RandomC (psource);
int len=result.size();//Длина комбинации fn
result.add((new Object[]{source[source.length-1]}));
for(int i=0;i<len;i++)
{
Object[] tmp=new Object[result.get(i).length+1];
for(int j=0;j<tmp.length-1;j++)
{
tmp[j]=result.get(i)[j];
}
tmp[tmp.length-1]=источник[source.length-1];
result.add(tmp);
}
}
вернуть результат;
}
статический ArrayList<Object[]> cmn(Источник Object[],int n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
если (п == 1)
{
for(int i=0;i<source.length;i++)
{
result.add(новый объект[]{источник[i]});
}
}
иначе, если (source.length==n)
{
результат.добавить(источник);
}
еще
{
Object[] psource=новый объект[source.length-1];
for(int i=0;i<psource.length;i++)
{
psource[i]=источник[i];
}
результат = cmn (psource, n);
ArrayList<Object[]> tmp=cmn(psource,n-1);
for(int i=0;i<tmp.size();i++)
{
Объект[] rs=новый Объект[n];
for(int j=0;j<n-1;j++)
{
rs[j]=tmp.get(i)[j];
}
rs[n-1]=источник[source.length-1];
result.add(rs);
}
}
вернуть результат;
}
}
3. Используйте идею динамического программирования для поиска перестановок и комбинаций.
Скопируйте код кода следующим образом:
пакет АКМ;
//Мощный поиск комбинаций чисел
публичный класс MainApp {
public static void main(String[] args) {
int[] num=new int[]{1,2,3,4,5};
Строка ул="";
//Находим количество комбинаций из 3 чисел
// count(0,str,num,3);
// Находим количество комбинаций 1-n чисел
счетчик1 (0, строка, число);
}
Private static void count1(int i, String str, int[] num) {
если (я == num.length) {
System.out.println(str);
возвращаться;
}
count1 (я+1, строка, число);
count1(i+1,str+num[i]+",",num);
}
Private static void count(int i, String str, int[] num,int n) {
если (п == 0) {
System.out.println(str);
возвращаться;
}
если (я == num.length) {
возвращаться;
}
count(i+1,str+num[i]+",",num,n-1);
count(я+1,str,num,n);
}
}
Ниже приводится расположение
Скопируйте код кода следующим образом:
пакет АКМ;
//Найти расположение, найти расположение после различных перестановок или комбинаций
импортировать java.util.Arrays;
импортировать java.util.Scanner;
публичный класс Demo19 {
частное статическое логическое значение f[];
public static void main(String[] args) {
Сканер sc=новый сканер(System.in);
int sz=sc.nextInt();
for(int i=0;i<sz;i++){
int sum = sc.nextInt ();
f = новое логическое значение [сумма];
Arrays.fill(f, true);
int[] num=new int[sum];
for(int j=0;j<sum;j++){
число[j]=j+1;
}
int nn=sc.nextInt();
Строка ул="";
счетчик (число, строка, nn);
}
}
/**
*
* @param num представляет массив, который нужно упорядочить.
* @param str Организованная строка
* @param nn Количество оставшихся элементов, которые необходимо упорядочить. Если требуется полная упорядоченность, nn — это длина массива.
*/
Private static void count(int[] num, String str, int nn) {
если(nn==0){
System.out.println(str);
возвращаться;
}
for(int i=0;i<num.length;i++){
если(!f[i]){
продолжать;
}
е[я]=ложь;
count(num,str+num[i],nn-1);
е[я]=истина;
}
}
}