1. バイナリ状態法を使用して順列と組み合わせを見つけます。この方法は比較的理解しやすいですが、演算効率は高くありません。
次のようにコードをコピーします。
java.util.Arraysをインポートします。
//バイナリアルゴリズムを使用して完全な配置を実行します
//カウント1:170187
//カウント2:291656
公開クラステスト {
public static void main(String[] args) {
ロングスタート=System.currentTimeMillis();
count2();
ロングエンド=System.currentTimeMillis();
System.out.println(end-start);
}
プライベート静的 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++){
文字列 str=Integer.toString(i,9);
int sz=str.length();
for(int j=0;j<9-sz;j++){
str="0"+str;
}
char[] temp=str.toCharArray();
Arrays.sort(temp);
文字列 gl=新しい文字列(一時);
if(!gl.equals("012345678")){
続く;
}
文字列結果="";
for(int m=0;m<str.length();m++){
result+=num[Integer.parseInt(str.charAt(m)+"")];
}
System.out.println(結果);
}
}
public static void 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=新しい int[9];
while(temp[0]<9){
temp[temp.length-1]++;
for(int i=temp.length-1;i>0;i--){
if(temp[i]==9){
温度[i]=0;
temp[i-1]++;
}
}
int []tt=temp.clone();
Arrays.sort(tt);
if(!Arrays.equals(tt,ss)){
続く;
}
文字列結果="";
for(int i=0;i<num.length;i++){
結果+=数値[温度[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]+",");
}
System.out.println();
}
}
// 配列の任意の組み合わせを検索します
static ArrayList<Object[]> RandomC(Object[] ソース)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(ソース.長さ==1)
{
result.add(ソース);
}
それ以外
{
オブジェクト[] psource=新しいオブジェクト[source.length-1];
for(int i=0;i<psource.length;i++)
{
psource[i]=ソース[i];
}
結果=ランダムC(pソース);
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);
}
}
結果を返します。
}
static ArrayList<Object[]> cmn(Object[] source,int n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(n==1)
{
for(int i=0;i<source.length;i++)
{
result.add(new Object[]{source[i]});
}
}
else if(source.length==n)
{
result.add(ソース);
}
それ以外
{
オブジェクト[] 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]=ソース[ソース.長さ-1];
result.add(rs);
}
}
結果を返します。
}
}
3. 動的プログラミングのアイデアを使用して順列と組み合わせを求める
次のようにコードをコピーします。
パッケージAcm;
//組み合わせ番号の強力な検索
パブリック クラス MainApp {
public static void main(String[] args) {
int[] num=new int[]{1,2,3,4,5};
文字列 str="";
// 3 つの数字の組み合わせの数を求める
// count(0,str,num,3);
// 1 ～ n の数字の組み合わせの数を求める
count1(0,str,num);
}
private static void count1(int i, String str, int[] num) {
if(i==num.length){
System.out.println(str);
戻る;
}
count1(i+1,str,num);
count1(i+1,str+num[i]+",",num);
}
private static void count(int i, String str, int[] num,int n) {
if(n==0){
System.out.println(str);
戻る;
}
if(i==num.length){
戻る;
}
count(i+1,str+num[i]+",",num,n-1);
count(i+1,str,num,n);
}
}
以下がアレンジメントです
次のようにコードをコピーします。
パッケージAcm;
//配置を見つけ、さまざまな順列または組み合わせ後の配置を見つけます
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=新しい int[合計];
for(int j=0;j<sum;j++){
num[j]=j+1;
}
int nn=sc.nextInt();
文字列 str="";
count(num,str,nn);
}
}
/**
*
※ @param numは配置する配列を表します
* @param str 配列された文字列
* @param nn 配置する必要がある残りの項目の数。完全な配置が必要な場合、nn は配列の長さです。
*/
private static void count(int[] num, String str, int nn) {
if(nn==0){
System.out.println(str);
戻る;
}
for(int i=0;i<num.length;i++){
if(!f[i]){
続く;
}
f[i]=false;
count(num,str+num[i],nn-1);
f[i]=true;
}
}
}