무작위 선택

당신은 우리가 데이터의 하위 집합을 찾을 수있는 방법을무작위 선택

Data=[ a1 a2 a3 a4..... an]; 0<ai<100

같은 1 차원 벡터 데이터를

는 가정 다음과 같은 질문에 대한 의견을 공유하시기 바랍니다 것입니다 같은

Data_subset=[ a3 a7 a8] or Data_subset=[ a1 a17 a81 a92 a93 a100 a101 ]

로 가장 잘 파악이 조건 : 어떤 ID abs(sum(Data_subset)-700)<10

그렇지?

넌

고유 = SUM (((N-1)^2 + N-1)/2) + N N 행 = 1 N에 의해 고유 집합 (무시 순서)의 수를 계산할 수

출처

2016-07-06 Karlo Gonzales

정확하게 해결하기가 어려울 것으로 알려진 [배낭 문제] (https://en.wikipedia.org/wiki/Knapsack_problem)와 매우 유사하게 보입니다. –

나는 그것을 [부분 집합 합 문제 ] (https://en.wikipedia.org/wiki/Subset_sum_problem). – beaker

"가장 양호한 조건"이라고 말하면,'abs (sum (Data_subset) -700) <10'을 true로 유지하는 부분 집합이 필요하거나 최소한의 값을 갖는 부분 집합을 원합니까? abs (합계 (Data_subset) -700)'? –

= 99

그래서 길이가 100 인 벡터에 대해서만 이것을 수행하면 166750 개의 고유 한 데이터 하위 세트가 생깁니다. 이 경우 각 하위 집합을 테스트하여 문제를 발생시키지 않아도됩니다. 즉, 생성 할 수있는 방법을 만들 수 있습니다.

matlab 함수 perms()와 같은 것을 사용할 수 있습니다. 벡터 permutation은 1e156 다른 순열과 같아야한다는 것을 제외하고는 벡터의 모든 순열을 제공합니다. 내가 생각할 수있는

유일한 부분적인 해결책은 randperm()를 사용하고 그 랜덤 순열

nPerms = 100 
    subSetsSaved = cell() 
    cellIndex=1; 
    for iRand=1:1:nPerms 
     randOrder = randperm(length(data)); 
     dataPerm = permute(data,randOrder); 
     for jSub=1:1:length(data) 
       subSet = dataPerm(1:jSub); 
       if (abs(sum(subSet)-700)<10) 
        subSetsSaved{cellIndex} = subSet; 
        cellIndex = cellIndex+1; 
       end 
      end 
    end

의 하위 집합을 테스트하는 루프를 만드는 것입니다 당신은 무작위로 생성을 시도하기 위해 임의의 순열 루프를 사용할 수 있습니다 모든 166750 개의 고유 한 하위 집합. 당신이해야 할 일은 무작위로 생성, 정렬 및 고유성 테스트입니다. 물론 이러한 솔루션은 효율성 측면에서 이상적이지 않습니다. 따라서 문제가 해결해야하거나 문제가 N = 100보다 훨씬 큰 경우 다른 방법이 필요합니다.

출처

2016-07-07 14:06:44 blindpanic

고유 한 하위 집합 수를 계산할 수 있는지 잘 모르겠습니다. 내가 볼 수있는 것은 바이너리입니다. 각 요소는 부분 집합에 있거나 포함되지 않으므로 고유 한 부분 집합의 수는'2^n'입니다. 여기서 n은 원본 벡터의 길이입니다. – beaker

무작위 선택

답변

관련 문제