Блог

У меня проблема с передачей подмножеств вектору. Я пытаюсь переписать код с Java на C . Есть какие-нибудь предложения? Предполагается, что программа выведет все возможные комбинации r элементов в заданном массиве размера n.

У меня проблема с передачей подмножеств вектору. Я пытаюсь переписать код с Java на C . Есть какие-нибудь предложения? Предполагается, что программа выведет все возможные комбинации r элементов в заданном массиве размера n.

Код

 // The main function that prints // all combinations of size r // in arr[] of size n. This function // mainly uses combinationUtil() vectorlt;vectorlt;intgt;gt; getCombinations(const vectorlt;intgt;amp; list, int r) {  // A temporary array to store  // all combination one by one // int data[r];  vectorlt;vectorlt;intgt;gt; resultSet = vectorlt;vectorlt;intgt;gt;();  //list = u  // Print all combination using  // temporary array 'data[]' // combinationUtil(arr, data, 0, n-1, 0, r);  return combinationUtil(list, list.size(), r, 0, vectorlt;intgt;(), 0, resultSet); }  /* arr[] ---gt; Input Array data[] ---gt; Temporary array to store current combination start amp; end ---gt; Starting and Ending indexes in arr[] index ---gt; Current index in data[] r ---gt; Size of a combination to be printed */ vectorlt;vectorlt;intgt;gt; combinationUtil(vectorlt;intgt; list, int n, int r, int index, vectorlt;intgt; result, int i, vectorlt;vectorlt;intgt;gt; resultSet) {  // Current combination is ready  // to be printed, print it  if (index == r) {  vectorlt;intgt; variant = vectorlt;intgt;();  for (int j = 0; j lt; r; j  ) {  variant.push_back(result.at(j)); "";  }  resultSet.push_back(variant);  return resultSet;  }   // replace index with all possible  // elements. The condition "end-i 1 gt;= r-index"  // makes sure that including one element  // at index will make a combination with  // remaining elements at remaining positions  if (i gt;= n) {return resultSet;}   // current is included, put next at next  // location  result.insert(result.begin()   index, list.at(i));  combinationUtil(list, n, r, index   1, result, i   1, resultSet);   // current is excluded, replace it with  // next (Note that i 1 is passed, but  // index is not changed)  combinationUtil(list, n, r, index, result, i   1, resultSet);  return resultSet; }  

Вы уверены, что достаточно хорошо знаете оба языка, чтобы выполнять перевод? например, ваш код создает множество копий векторов. На самом деле это самая используемая операция там. И эта часть выглядит подозрительно, правильно ли она работает?

 vectorlt;vectorlt;intgt;gt; calculate(vectorlt;intgt; inputSet) {  log(inputSet);  vectorlt;intgt; result = vectorlt;intgt;();   for (int i = 0; i lt; inputSet.size(); i  ) {  result.push_back(inputSet.at(i));  if (sum(result) gt; sum(inputSet) - sum(result)) {  cout lt;lt; i   1 lt;lt; "elementow" lt;lt; endl;  //tutaj ta funkcja zwracająca pozdbiory  break;  }  }  cout lt;lt; "Nie znaleziono zbioru spelniajacego wymagania" lt;lt; endl;  return {}; }  int sum(vectorlt;intgt; vector) {  return accumulate(vector.begin(), vector.end(), 0); }  

calculate всегда возвращает пустой вектор. Он выполняет N*3 2 копии векторных inputSet и суммарных O(3*N*(N 1)) операций, где N — размер этого вектора. Возможно, вам нужно присвоить псевдоним своим типам, например, и передать значение:

 using VectorInt = vectorlt;intgt;;  using VectorInt2D = vectorlt;vectorlt;intgt;gt;gt;;    void /*VectorInt2D*/ calculate(const VectorIntamp; inputSet) {  log(inputSet);  int result = 0, inputSum = sum(inputSet);     for (int i = 0; i lt; inputSet.size(); i  ) {  result  = inputSet[i];  if (result gt; inputSum - result ) {  cout lt;lt; i   1 lt;lt; "elementow" lt;lt; endl;  //tutaj ta funkcja zwracająca pozdbiory  break;  }  }  cout lt;lt; "Nie znaleziono zbioru spelniajacego wymagania" lt;lt; endl;  //return {}; // what we return here?  }    int sum(const VectorIntamp; vector) {  return accumulate(vector.begin(), vector.end(), 0);  }  

Я подозреваю, что вы не понимаете, что в C все параметры передаются по значению, в то время как в Java все параметры передаются по ссылке. Функция с подписью

 vectorlt;vectorlt;intgt;gt; combinationUtil(vectorlt;intgt; list, int n, int r, int index,  vectorlt;intgt; result, int i, vectorlt;vectorlt;intgt;gt; resultSet)  

невозможно изменить вектор, переданный в качестве аргумента для параметра resultSet . Может быть, даже не стоит пытаться, но это выглядит необходимым для рекурсии.

 vectorlt;vectorlt;intgt;gt; getCombinations(const vectorlt;intgt;amp; list, int r) {  // A temporary array to store  // all combination one by one // int data[r];  vectorlt;vectorlt;intgt;gt; resultSet = vectorlt;vectorlt;intgt;gt;();  //list = u  // Print all combination using  // temporary array 'data[]' // combinationUtil(arr, data, 0, n-1, 0, r);  return combinationUtil(list, list.size(), r, 0, vectorlt;intgt;(), 0, resultSet); }  

resultSet это не временное явление. Это локальная автоматическая переменная, и она копируется при передаче combinationUtil и копируется снова при возврате. Он не может быть изменен рекурсивными вызовами combinationUtil . Все это выглядит ущербно и, казалось, работало только на языке оригинала.

Декларация:

 vectorlt;vectorlt;intgt;gt; combinationUtil(vectorlt;intgt; list, int n, int r, int index, vectorlt;intgt; result, int i, vectorlt;vectorlt;intgt;gt; resultSet); // lt;-- returns a vector of vectors  

Звонки:

 result.insert(result.begin()   index, list.at(i)); combinationUtil(list, n, r, index   1, result, i   1, resultSet); // lt;-- the result is discarded  // current is excluded, replace it with // next (Note that i 1 is passed, but // index is not changed) combinationUtil(list, n, r, index, result, i   1, resultSet); // lt;-- the result is discarded  return resultSet;  

Если вам не нужно возвращаемое значение, зачем вы его возвращаете?

Этот вид кодирования может работать в Java, где большинство вещей являются ссылками, но не в C . combinationUtil получает все аргументы по значению и не использует глобальных переменных, поэтому единственный способ, которым он может повлиять на окружение, — это вернуть значение. Если вы отбросите возвращаемое значение, вы просто превратите функцию в (очень, очень дорогую) операцию без операции.

Один из способов устранить проблему-перестать отбрасывать возвращаемое значение.

 resultSet = combinationUtil(list, n, r, index, result, i   1, resultSet);   

Более эффективным способом является передача resultSet по ссылке и прекращение возврата значения из нее, так как теперь функция работает, изменяя свой аргумент.

 void combinationUtil(vectorlt;intgt; list, int n, int r, int index, vectorlt;intgt; result, int i, vectorlt;vectorlt;intgt;gt;amp; resultSet); // adjust calls accordingly  

Это не решает проблему сложности всего решения. Алгоритм комбинаций является экспоненциальным (n выбирает r, чтобы быть точным), и никакое количество манипуляций со ссылками не может этого изменить. Проблема, как я понимаю, может быть решена с помощью гораздо более асимптотически эффективного алгоритма.

Не имеет отношения к вашему коду.

Существует множество возможных решений

• Используя рекурсию. Это сложное и самое неэффективное решение
• Использование массива селекторов и его перестановок. Это стандартный подход по умолчанию.

Ниже я покажу стандартный подход по умолчанию.

Идея заключается в том, что у нас есть массив селекторов, параллельный исходному массиву данных. В этом массиве селекторов мы задаем столько битов, сколько должно быть по размеру подмножества. А затем мы выполняем все перестановки для массива селекторов и используем значение из исходного массива, если установлен соответствующий селектор.

Пример для размера подмножества 2:

 Base Data: 1,2,3,4   ^ ^ ^ ^  | | | |  Selector: 0,0,1,1 --gt; 3,4  0,1,1,0 --gt; 2,3  0,1,0,1 --gt; 2,4  1,0,0,1 --gt; 1,4  1,0,1,0 --gt; 1,3  1,1,0,0 --gt; 1,2  

Тогда действительно простой код будет выглядеть так:

 #include lt;iostreamgt; #include lt;vectorgt; #include lt;algorithmgt; #include lt;iteratorgt;  using MyType = int; using Data = std::vectorlt;intgt;; using Combinations = std::vectorlt;Datagt;;  Combinations getCombinations(const Dataamp; data, const size_t subSetSize) {   // Define the selector with the same size as the input data vector  std::vectorlt;boolgt; selector(data.size());   // Set subSetSize elements in the selector element to true  std::fill(selector.begin(), std::next(selector.begin(),subSetSize), true);   // Here we will store the resulting values  Combinations result{};   // Here we will create the subsets. All values will be overwritten in every loop run. No need for clear or something  Data subset(subSetSize);   do {  // Create the subset  std::copy_if(data.begin(), data.end(), subset.begin(), [amp;, i=0u](const MyType m) mutable { return selector[i  ]; });  result.push_back(subset);   // Create the next permutation  } while (std::prev_permutation(selector.begin(), selector.end()));   return result; }  int main() {  Data data{ 1,2,3,4,5,6,7,8 };   for (const Dataamp; d : getCombinations(data, 4)) {  for (const MyTypeamp; t : d) std::cout lt;lt; t lt;lt; ' ';  std::cout lt;lt; 'n';  } }