1. Utilisez la méthode de l'état binaire pour trouver des permutations et des combinaisons. Cette méthode est relativement facile à comprendre, mais son efficacité opérationnelle n'est pas élevée. De petites permutations et combinaisons de données peuvent être utilisées.
Copiez le code comme suit :
importer java.util.Arrays ;
//Utiliser un algorithme binaire pour effectuer un arrangement complet
//compte1:170187
//compte2:291656
test de classe publique {
public static void main (String[] arguments) {
long start=System.currentTimeMillis();
compte2();
extrémité longue = System.currentTimeMillis();
System.out.println(fin-début);
}
compte de vide statique privé2(){
int[] num=nouveau int []{1,2,3,4,5,6,7,8,9};
pour(int i=1;i<Math.pow(9, 9);i++){
String str=Integer.toString(i,9);
int sz=str.length();
pour(int j=0;j<9-sz;j++){
str="0"+str;
}
char[] temp=str.toCharArray();
Arrays.sort(temp);
Chaîne gl=nouvelle Chaîne(temp);
si(!gl.equals("012345678")){
continuer;
}
Résultat de chaîne="";
pour(int m=0;m<str.length();m++){
result+=num[Integer.parseInt(str.charAt(m)+"")];
}
System.out.println(résultat);
}
}
public static void count1(){
int[] num=nouveau int []{1,2,3,4,5,6,7,8,9};
int[] ss=nouveau int []{0,1,2,3,4,5,6,7,8};
int[] temp=nouveau int[9];
pendant que(temp[0]<9){
temp[temp.length-1]++;
pour(int i=temp.length-1;i>0;i--){
si(temp[i]==9){
temp[i]=0;
temp[i-1]++;
}
}
int []tt=temp.clone();
Tableaux.sort(tt);
if(!Arrays.equals(tt,ss)){
continuer;
}
Résultat de chaîne="";
pour(int i=0;i<num.length;i++){
résultat+=num[temp[i]];
}
System.out.println(résultat);
}
}
}
2. Utilisez la pensée récursive pour trouver des permutations et des combinaisons, ce qui nécessite une grande quantité de code.
Copiez le code comme suit :
pratique du forfait ;
importer java.util.ArrayList ;
importer java.util.List ;
classe publique Test1 {
/**
* @param arguments
*/
public static void main (String[] arguments) {
// TODO Stub de méthode généré automatiquement
Objet[] tmp={1,2,3,4,5,6};
// ArrayList<Object[]> rs=RandomC(tmp);
ArrayList<Object[]> rs=cmn(tmp,3);
pour(int i=0;i<rs.size();i++)
{
// System.out.print(i+"=");
pour(int j=0;j<rs.get(i).length;j++)
{
System.out.print(rs.get(i)[j]+",");
}
System.out.println();
}
}
// Recherche n'importe quelle combinaison d'un tableau
ArrayList statique<Object[]> RandomC(Source de l'Object[])
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
si(source.length==1)
{
result.add(source);
}
autre
{
Objet[] psource=nouveau Objet[source.length-1];
pour(int i=0;i<psource.length;i++)
{
psource[i]=source[i];
}
résultat=RandomC(psource);
int len=result.size();//La longueur de la combinaison fn
result.add((new Object[]{source[source.length-1]}));
pour(int i=0;i<len;i++)
{
Object[] tmp=new Object[result.get(i).length+1];
pour(int j=0;j<tmp.length-1;j++)
{
tmp[j]=result.get(i)[j];
}
tmp[tmp.length-1]=source[source.length-1];
result.add(tmp);
}
}
renvoyer le résultat ;
}
ArrayList statique<Object[]> cmn(Object[] source,int n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
si(n==1)
{
pour(int i=0;i<source.length;i++)
{
result.add(new Object[]{source[i]});
}
}
sinon si(source.length==n)
{
result.add(source);
}
autre
{
Objet[] psource=nouveau Objet[source.length-1];
pour(int i=0;i<psource.length;i++)
{
psource[i]=source[i];
}
résultat=cmn(psource,n);
ArrayList<Object[]> tmp=cmn(psource,n-1);
pour(int i=0;i<tmp.size();i++)
{
Objet[] rs=nouveau Objet[n];
pour(int j=0;j<n-1;j++)
{
rs[j]=tmp.get(i)[j];
}
rs[n-1]=source[source.length-1];
result.add(rs);
}
}
renvoyer le résultat ;
}
}
3. Utiliser l'idée de programmation dynamique pour rechercher des permutations et des combinaisons
Copiez le code comme suit :
paquet Acm ;
//Recherche puissante de numéros de combinaison
classe publique MainApp {
public static void main (String[] arguments) {
int[] num=nouveau int[]{1,2,3,4,5};
Chaîne str="";
//Trouver le nombre de combinaisons de 3 nombres
// compte(0,str,num,3);
// Trouver le nombre de combinaisons de nombres 1-n
count1(0,str,num);
}
private static void count1 (int i, String str, int[] num) {
si(i==num.longueur){
System.out.println(str);
retour;
}
count1(i+1,str,num);
count1(i+1,str+num[i]+",",num);
}
nombre de vides statiques privés (int i, String str, int[] num,int n) {
si(n==0){
System.out.println(str);
retour;
}
si(i==num.length){
retour;
}
count(i+1,str+num[i]+",",num,n-1);
compte(i+1,str,num,n);
}
}
Voici l'arrangement
Copiez le code comme suit :
paquet Acm ;
//Trouver l'arrangement, trouver l'arrangement après diverses permutations ou combinaisons
importer java.util.Arrays ;
importer java.util.Scanner ;
classe publique Démo19 {
booléen statique privé f[];
public static void main (String[] arguments) {
Scanner sc = nouveau scanner (System.in);
int sz=sc.nextInt();
pour(int i=0;i<sz;i++){
int sum=sc.nextInt();
f=nouveau booléen[somme];
Arrays.fill(f, vrai);
int[] num=nouveau int[somme];
pour(int j=0;j<somme;j++){
num[j]=j+1;
}
int nn=sc.nextInt();
Chaîne str="";
count(num,str,nn);
}
}
/**
*
* @param num représente le tableau à organiser
* @param str Chaîne arrangée
* @param nn Le nombre d'éléments restants qui doivent être organisés. Si un arrangement complet est requis, nn est la longueur du tableau.
*/
nombre de vides statiques privés (int[] num, String str, int nn) {
si(nn==0){
System.out.println(str);
retour;
}
pour(int i=0;i<num.length;i++){
si(!f[i]){
continuer;
}
f[i]=faux;
count(num,str+num[i],nn-1);
f[i]=vrai ;
}
}
}