Получение всех комбинаций числа в C++

Question

Мне нужно получить все возможные комбинации данного набора. Например, если: [1, 4, 7], полученные в результате комбинации должны быть:

• 111, 114, 117, 141, 144, 147, 171, 174, 177, 411, 414, 417, 441 , 444, 447, 471, 474, 477, 711, 714, 717, 741, 744, 747, 771, 774, 777.

Я попытался с помощью next_permutation метод, но это не то, что я хочу (это не возвращает такие значения, как 111, 144, 717 и т. д.).

Так что я могу сделать это на C++? Обратите внимание, что я полный новичок.

Заранее спасибо.

Answer 1

Внимательно посмотрите на цифры: Все перечисленные вами номера также могут быть представлены в виде списка {11,14,17,41,44,47,71,74,77} с префиксом 1, один раз с 4 и один раз с 7. Это указывает на общее правило:

Строки с 3 номерами набора {1,4,7} построены путем взятия строк с 2 номерами одного и того же набора и добавления каждого элемента множества.

Обобщите 3 и 2 в этом правиле, реализуйте полученную идею с рекурсией, и у вас есть алгоритм для вашей проблемы.

В качестве заметки по внедрению C++ убедитесь, что для представления чисел используются целые числа вместо целых чисел. Эта проблема не является арифметикой и плотно связана с представлением base-10. Строки сделают вашу жизнь намного легче.

Answer 2

Создайте массив со значениями, например. {1, 4, 7}.

Используйте длину (массив) для циклов, каждая с итерациями длины (массива).

В самой внутренней выходной контур 100 * массив [я] + 10 * массив [J] + массив [к]

Если максимальная длина не известна, то вы вместо того, чтобы использовать рекурсию, например, псевдокод:

void Solve(int[] array, int length, int position, int sum) 
{ 
    position++; 
    sum *= 10; 

    for (int cnt = 0; cnt < length; cnt++) 
    { 
     int tempsum = sum + array[cnt]; 

     if (position == length) 
      output(tempsum); 
     else 
      Solve(array, length, position, tempsum); 
    } 
} 

Answer 3

Посмотрите мой ответ здесь: PHP take all combinations

Подсказка: Это не C++ код, но вы получите идею. (Я бы предложил использовать рекурсию)

Answer 4

Создайте вектор целых чисел (так называемый vector), равный по размеру количеству элементов в вашем наборе. Инициализируйте каждую запись до 0. Затем следуйте этому алгоритму:

1) Прогулка vector, выводя соответствующие элементы. (Итак, если вектор равен 0,1,1, а множество - [9,8,7], вывод 988 - нулевой элемент, первый элемент, первый элемент.)

2) Установите целое число, называемое element - 0.

3) Increment vector[element]. Проверьте, соответствует ли vector[element] числу элементов в наборе. Если не перейти к этапу 1.

4) Установите vector[element] на ноль. Increment element. Если element меньше количества элементов в наборе, перейдите к шагу 3.

5) Стоп. Вы сделали.

Answer 5

Ну, я взял на себя смелость, чтобы попытаться выполнить задачу. Я хотел немного отбросить свои знания по алгоритму. Он оказался так:

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <set> 
using namespace std; 

vector<int> allowedNumbers; 

bool my_next_perm(vector<int>::iterator& begin, vector<int>::iterator& end) { 
    for (vector<int>::iterator itr = end - 1; ; --itr) 
    { 
     if (*itr != allowedNumbers.back()) 
     { 
      *itr = *upper_bound(allowedNumbers.begin(), allowedNumbers.end(), *itr); 
      while ((++itr) != end) { 
       *itr = allowedNumbers[0]; 
      } 
      return true; 
     } 
     if (itr == begin) 
     { 
      return false; 
     } 
    } 
} 
void printAllPermutationsWithRepetitions(vector<int>& v) 
{ 
    int n = v.size(); 
    set<int> allNumbers; 
    for (int i = 0; i < n; i++) 
    { 
     allNumbers.insert(v[i]); 
    } 
    for (set<int>::iterator itr = allNumbers.begin(); itr != allNumbers.end(); ++itr) { 
     allowedNumbers.push_back(*itr); 
    } 
    for (int i = 0; i < n; i++) { 
     v[i] = allowedNumbers[0]; 
    } 

    do { 
     for (int i = 0; i < n; i++) { 
      if (i != 0) cout << " "; 
      cout << v[i]; 
     } 
     cout << endl; 
    } while(my_next_perm(v.begin(), v.end())); 
} 

int main (int argc, char *argv[]) { 
    vector<int> v; 
    v.push_back(7); 
    v.push_back(1); 
    v.push_back(3); 
    printAllPermutationsWithRepetitions(v); 
    return 0; 
} 

Реализация только немного неоптимальным (потому что я использую upper_bound).

Answer 6

Вы эффективно рассчитываете с базой 3 от 000 до 222, просматривая свой массив [1, 4, 7] с этими цифрами в качестве индексов. Обобщая это работать с массивом произвольного размером входным:

int n = digits.size(); 
int n_n = std::pow(n, n); 
for (int i = 0; i < n_n; ++i) 
{ 
    int x = i; 
    for (int j = 0; j < n; ++j) 
    { 
      cout << digits[x % n]; 
      x /= n; 
    } 
    cout << ' '; 
} 

Answer 7

Это простым способом сделать это. Вы можете принять любой номер в качестве входных данных пользователя, например 147, и распечатать все перестановки as: 111, 114, 117, 141, 144, 147, 171, 174, 177, 411, 414, 417, 441, 444, 447, 471, 474, 477, 711, 714, 717, 741, 744, 747, 771, 774, 777.

#include <iostream> 
#include <cstdlib> 
#include <cmath> 
using namespace std; 

bool Search(int A[],int num,int length) 
    { 
     for(int i = 0;i<length;i++) 
      if(A[i] == num) 
       return 1; 
     return 0; 
    } 


    int main() 
    { 
     int n; 
     cout << "Please Enter a Number\n"; 
     cin>>n; 
     int num = n, k = 1; 
     int count = 0; 
     while(num>0) 
     { 
      num/=10; 
      count++; 
     } 
     cout<<"The All Permutations of " <<n<<" are: "<<endl; 
     num = n; 
     int *A = new int[count]; 

     for(int i = 0;i<count;i++) 
     { 
      A[i] = num%10; 
      num/=10; 
     } 


     int fact = pow(count,count); 
     int *Ar = new int[fact]; 
     int *B = new int[count]; 
     int value,number = 0; 

     for(int i = 0;i<fact;) 
     { 

      for(int j = 0;j<count;++j) 
      { 
       value = (rand()%count); 

       B[j] = value; 
      } 

      for(int k= 0;k<count;k++) 
       number = number + A[B[k]]*pow(10,k); 

      if(Search(Ar,number,fact) == 0) 
      { 
       cout<<k++<<". "<<number<<endl; 
       Ar[i] = number; 
       ++i; 
      } 
      number = 0; 

     } 

     return 0; 
    }