回傳i<j<k的所有元素組合的正確演算法是什么

我必須在具有索引 i,j,k 的陣列 a[] 中找到所有組合，使得 i<j<k 并且必須為每個組合執行一個操作，例如在陣列 int a[] = {12,1 ,34,32} 的組合是 {12,1,34},{12,1,32},{12,34,32}。{1,34,32}

我嘗試了遞回方式并將所有組合存盤在一個集合中，這樣如果我再次訪問相同的組合，我只會通過從集合中檢查它來從那里回傳

我的代碼是這樣的，但我正在為大型案例獲得 TLE 任何人都可以為我提供最有效的方法

 static Set<String> set = new HashSet<>();
 static int sum = 0;

    static void solve(int i,int j,int k,int[] a){
        if(i>=j || j>=k ||k>=a.length){
            return;
        }
        
        //combination
        String pre = String.valueOf(i) String.valueOf(j) String.valueOf(k);
        if(set.contains(pre)){
            return;
        }

        //operation to perform for every combination
        int v = (a[i] | a[j] | a[k]) ^ (a[i] ^ a[j] ^ a[k]);
        sum = sum v;

        solve(i,j,k 1,a);
        solve(i,j 1,k,a);
        solve(i 1,j,k,a);
    }

uj5u.com熱心網友回復：

對于三個索引，創建三個回圈更簡單。為了簡單起見，我還添加了兩個二進制操作的預計算并洗掉了集合檢查。

static int solve(int[] a){
    int leng = a.length;
    int sum = 0;
    for (i=0; i < leng-2; i  )   {
       for (j=i 1; j < leng - 1; j  )   {
           int ijor = a[i] | a[j];
           int ijxor = a[i] ^ a[j];
           for (k=j 1; k < leng; k  )   {
              //operation to perform for every combination
             sum = sum   (ijor | a[k]) ^ (ijxor ^ a[k]);
           }
        }
     }
     return sum; 
}

uj5u.com熱心網友回復：

我看到您正在使用 java，但是，我可以使用 python 提供答案，但我確信 java 中也有等效的操作：

from itertools import combinations
def combs_tri(X):
    lenght=len(X)
    num_of_zeros=lenght-3
    def factorial(n):
        m=1
        for x in range(1,n 1):
            m=m*x
        return m
    def num_of_comb(n,z):
        return int(factorial(lenght)/(factorial(z)*factorial(lenght-z)))
    count=num_of_comb(lenght,3)
    def create_boolean_array(num_of_zeros,count,lenght):
        Arr=np.zeros((count,lenght))
        combs=list(combinations(range(lenght), 3))
        for i,comb in enumerate(combs):
            Arr[i,comb]=1
        return Arr
    repeated_list=np.repeat([X],count,axis=0)
    bool_mask=create_boolean_array(num_of_zeros,count,lenght)
    return repeated_list[bool_mask.astype(bool)].reshape((int(count)),3)

功能說明

階乘：執行數學運算階乘，即 n!=n(n-1) (n-2) ...

num_of_comb：執行數學組合運算并回傳數值結果。

create_boolean_array：創建一個布爾掩碼以獲取陣列元素的所有可能組合。->combinations()：回傳組合 Ex/combinations([1,2,3],2)=[(1,2),(1,3),(2,3)]

->np.repeat([X],count,axis=0) 按給定的計數重復給定的串列。計數在這里表示組合的數量（3）。

例如/ np.repeat([1,2,3,4],count,axis=0)=np.array([[1,2,3,4],[1,2,3,4],[1 ,2,3,4],[1,2,3,4]])

在大多數情況下，陣列操作比 for 回圈快得多。

uj5u.com熱心網友回復：

我認為這是一個非常簡單的問題，只有 3 個回圈。我用 C 寫過代碼，但你一定會明白的：

#include <vector>
#include <iostream>

void print_all(const std::vector<int>& arr){
    for (size_t i = 0; i < arr.size() - 2; i  ) {
        for (size_t j = i   1; j < arr.size() - 1; j  ) {
            for (size_t k= j   1; k < arr.size(); k  ) {
                if ((arr[i] < arr[j]) || (arr[i] > arr[j] && arr[i] < arr[k]))
                    std::cout << "[" << arr[i] << "," << arr[j] << "," << arr[k] << "]\n";
            }
        }
    }
}

int main() {
    std::vector<int> arr = {12, 1, 34, 32};
    print_all(arr);
}

對于條件，對于元組(a, b, b)：

1. 如果a<b，那么您可以選擇任何c并a<b<c以最多 1 次移動到達。
2. 如果a>b，你需要切換它們，那么都c需要大于a。

標籤：

上一篇：檢查樹中從A到B的路徑中是否存在節點

下一篇：保存計算結果以供重復使用，同時管理記憶體消耗