Java アルゴリズムで完全な置換を実装する方法

アルゴリズム 1

は再帰とバックトラッキングに基づいています。 1、2、3を並べるときは、まず3から2に戻り、他に考えられる状況がないことを確認してから、1に戻り、1、3、2を並べ、他の状況がある場合まで戻ります。 、つまりルートノード、そして最初の位置として2を配置するとき、上記のプロセスを繰り返して、考えられるすべての結果をresに入れます。

コード:

import java.util.ArrayList;
import java.util.List;
 
public class h718_1 {
 
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] arr = {1,2,3};
 
        h718_1 h2 = new h718_1();
        h2.dfs(arr,new ArrayList<>());
        for (List<Integer> re : res) {
            System.out.println(re);
        }
 
    }
 
    public List<List<Integer>> dfs( int[] arr,List<Integer> list){
        List<Integer> temp = new ArrayList<>(list);
        if (arr.length == list.size()){
            res.add(temp);
        }
        for (int i=0;i<arr.length;i++){
            if (temp.contains(arr[i])){
                continue;
            }
            temp.add(arr[i]);
            dfs(arr,temp);
            temp.remove(temp.size()-1);
        }
        return res;
    }
 
}

アルゴリズム 2

位置を交換することで完全な配置を実現: セットが {1, 2, 3 であると仮定します。 , 4 };

ループ交換位置: 1 と 1 交換; 1 と 2 交換; 1 と 3 交換; 1 と 4 交換;

各交換はより小さいセットを再帰的に呼び出します:

例: 1 と 1 の最初の交換では、1 が最初の位置にあると判断されるため、これは {1} 再帰交換 {2,3,4} と見なすことができます;

最初の交換1 と 1 の交換 2 の交換により、2 が最初にあると判断されるため、{2} とみなすことができます。再帰的交換 {1,3,4};

1 の最初の交換3 は 3 が最初の位置にあると判断するため、{3} 再帰交換 {1,2,4} と見なすことができます。

1 と 4 の最初の交換により、4 が最初の位置にあると判断されます。場所なので、{4} 再帰交換 {1,2,3};

などとみなすことができます。

コード:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class h718_2 {
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
 
        int[] arr = {1,2,3};
        h718_2 h3 = new h718_2();
        h3.pailie_swap(0,arr);
 
    }
    public void pailie_swap(int index, int[] arr){
        if (arr.length==index){
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = index;i<arr.length;i++){
            swap(i,index,arr);
            pailie_swap(index+1,arr);
            swap(i,index,arr);
        }
 
    }
 
    public void swap(int i,int j ,int[] arr){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
 
    }
}

アルゴリズム 3

要素を追加することで完全な配置を実現できます:

最初にリストを定義し、最初の要素をその中に入れます。残りの要素を以前のセット要素のすべての可能な位置に挿入して、新しいリストを生成します。

例: {1,2,3,4} の完全な配置を実装します。

最初に、リストに追加される最初の要素は {1} です。次に、2 番目の要素 2 を {1} の前後 2 つの位置に挿入して新しいリスト {21, 12} を形成し、3 番目の要素 3 をすべての位置に挿入します。それぞれリストの要素です。位置は {321, 231, 213, 312, 132, 123} などです。

コード:

import java.util.ArrayList;
 
public class h718_3 {
 
    public static void main(String[] args) {
        String aa = "123";
        h718_3 h4 = new h718_3();
        ArrayList<String> res = new ArrayList<>();
        res = h4.getPermutation0(aa);
 
        for (String re : res) {
            System.out.println(re);
        }
 
    }
 
    public ArrayList<String> getPermutation0(String A) {
        int n = A.length();
        ArrayList<String> res = new ArrayList<>();
        res.add(A.charAt(0) + "");//初始化,包含第一个字符
 
        for (int i = 1; i < n; i++) {//第二个字符插入到前面生成集合的每个元素里面
            ArrayList<String> res_new = new ArrayList<>();
            char c = A.charAt(i);//新字符
            for (String str : res) {//访问上一趟集合中的每个字符串
                //  插入到每个位置,形成一个新串
                String newStr = c + str;//加在前面
                res_new.add(newStr);
                newStr = str + c;//加在后面
                res_new.add(newStr);
                //加在中间
                for (int j = 1; j < str.length(); j++) {
                    newStr = str.substring(0, j) + c + str.substring(j);
                    res_new.add(newStr);
                }
            }
            res = res_new;//更新
 
        }
        return res;
    }
}

以上がJava アルゴリズムで完全な置換を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。