1. 순열 및 조합을 찾기 위해 이진 상태 방법을 사용합니다. 이 방법은 비교적 이해하기 쉽지만 작은 데이터 순열 및 조합을 사용할 수 있습니다.
다음과 같이 코드 코드를 복사합니다 .
import java.util.Arrays;
//이진 알고리즘을 사용하여 전체 정렬을 수행합니다.
//count1:170187
//count2:291656
공개 수업 테스트 {
공개 정적 무효 메인(String[] args) {
긴 시작=System.currentTimeMillis();
카운트2();
긴 끝=System.currentTimeMillis();
System.out.println(끝-시작);
}
개인 정적 무효 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(임시);
문자열 gl=new String(temp);
if(!gl.equals("012345678")){
계속하다;
}
문자열 결과="";
for(int m=0;m<str.length();m++){
result+=num[Integer.parseInt(str.charAt(m)+"")];
}
System.out.println(결과);
}
}
공개 정적 무효 개수1(){
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[] 임시=새로운 int[9];
동안(온도[0]<9){
온도[temp.length-1]++;
for(int i=temp.length-1;i>0;i--){
if(온도[i]==9){
온도[i]=0;
온도[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. 재귀적 사고를 사용하여 많은 양의 코드가 필요한 순열과 조합을 찾습니다.
다음과 같이 코드 코드를 복사합니다 .
패키지실습;
import java.util.ArrayList;
java.util.List 가져오기;
공개 클래스 Test1 {
/**
* @param 인수
*/
공개 정적 무효 메인(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[]> 결과=new ArrayList<Object[]>();
if(소스.길이==1)
{
결과.추가(소스);
}
또 다른
{
개체[] 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];
결과.추가(tmp);
}
}
결과 반환;
}
static ArrayList<Object[]> cmn(Object[] 소스,int n)
{
ArrayList<Object[]> 결과=new ArrayList<Object[]>();
만약(n==1)
{
for(int i=0;i<source.length;i++)
{
result.add(new Object[]{source[i]});
}
}
그렇지 않은 경우(source.length==n)
{
결과.추가(소스);
}
또 다른
{
개체[] 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];
결과.추가(rs);
}
}
결과 반환;
}
}
3. 순열과 조합을 찾기 위해 동적 프로그래밍 아이디어를 활용하세요
다음과 같이 코드 코드를 복사합니다 .
패키지 Acm;
//조합 숫자에 대한 강력한 검색
공개 클래스 MainApp {
공개 정적 무효 메인(String[] args) {
int[] num=new int[]{1,2,3,4,5};
문자열 str="";
//3개 숫자의 조합 개수 구하기
// 개수(0,str,num,3);
// 1~n 숫자의 조합 개수를 구합니다.
count1(0,str,num);
}
private static void count1(int i, String str, int[] num) {
if(i==숫자.길이){
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==숫자.길이){
반품;
}
count(i+1,str+num[i]+",",num,n-1);
개수(i+1,str,num,n);
}
}
다음은 정리입니다
다음과 같이 코드 코드를 복사합니다 .
패키지 Acm;
//배열 찾기, 다양한 순열이나 조합 후 배열 찾기
import java.util.Arrays;
java.util.Scanner 가져오기;
공개 클래스 Demo19 {
개인 정적 부울 f[];
공개 정적 무효 메인(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();
문자열 str="";
개수(숫자,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]=거짓;
개수(숫자,str+숫자[i],nn-1);
f[i]=참;
}
}
}