打印所有子向量组合 + 问题
Print All Subvector Combinations + Issue
我正在尝试创建一个工具，让我的生活更轻松，以便根据数字加法设置配置设置列表，以指示应启用哪些功能。我使用的是 2 的幂列表，从 1 到 512 (1,2,4,8,16,32,64,128,256,512)。
手动检查并创建一个列表，列出哪些值将启用哪些功能会非常耗时，因此我尝试以编程方式进行，然后将输出保存到文件中。但是，我 运行 遇到了寻找合适解决方案的问题。
我已经阅读了 Google 中关于该主题的来自 SO 和其他编码论坛的几乎所有问题，并且所有问题都涉及线性组合。这是我能够做到的，我有这个示例代码，我修改了它，然后在以下基础上构建了我的工具：
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
// A is the array that contains the numbers
// comb is an array of size k that will hold all possible combinations
// n is the size of input array
// k is 1 less than the size of combination i.e. we want to find out 4C2 k =1
// current_k is the variable that makes us simulates k loops in a recursive function
void combinations(int A[], int comb[], int start, int n, int current_k, int k){
int sum = 0;
if (k < 0)
return;
// Base case just print all the numbers 1 at a time
if (k == 0){
for (int i = 0; i < n; i++)
cout << A[i] << endl;
}
// current_k goes from 0 to k-1 and simulates a total of
// k iterations
if (current_k < k){
// if current_k = 0, and k = 3 (i.e. we need to find combinations of 4)
// then we need to leave out 3 numbers from the end because there are 3
// more nested loops
for (int i = start; i < n - (k - current_k); i++){
// Store the number in the comb array and recursively call with the remaining sub-array
comb[current_k] = A[i];
// This will basically pass a sub array starting at index 'start' and going till n-1
combinations(A, comb, i+1, n, current_k+1, k);
}
}
else if (current_k == k){
for (int i = start; i < n; i++){
comb[current_k] = A[i];
for (int j = 0; j <= k; j++){
sum += comb[j];
}
cout << sum << endl;
sum = 0;
}
}
else
return;
}
int main(){
int n;
cout << "Enter the 'n' " << endl;
cin >> n;
int *A = new int[n];
for (int i = 0; i < n; i++)
A[i] = i+1;
int k;
cout << "Enter 'k'" << endl;
cin >> k;
int *comb = new int[k];
combinations(A, comb, 0, n, 0, k-1);
system("pause");
return 0;
}
唯一的问题是我还需要 non-linear 组合。像 1+64+256 这样的东西。这是否也能够拾取这些组合？我也有一个问题，我将在 post 我的代码后解释。这是我为此使用的实际代码：
#include <iostream>
#include <vector>
#include <string>
#include "mcl.h"
using std::cout;
using std::vector;
using std::string;
using std::cin;
using std::endl;
static vector<string> results;
// A is the array that contains the numbers
// comb is an array of size k that will hold all possible combinations
// n is the size of input array
// k is 1 less than the size of combination i.e. we want to find out 4C2 k =1
// current_k is the variable that makes us simulates k loops in a recursive function
void combinations(vector<mcl> A, vector<mcl> comb, int start, int n, int current_k, int k){
string sum;
string sNames;
int sCodes = 0;
if (k < 0)
k = 0;
// Base case just print all the numbers 1 at a time
if (k == 0){
for (int i = 0; i < n; i++)
cout << A.at(i).getCode() << " - " << A.at(i).getName() << endl;
return;
}
// current_k goes from 0 to k-1 and simulates a total of
// k iterations
if (current_k < k){
// if current_k = 0, and k = 3 (i.e. we need to find combinations of 4)
// then we need to leave out 3 numbers from the end because there are 3
// more nested loops
for (int i = start; i < n - (k - current_k); i++){
// Store the number in the comb array and recursively call with the remaining sub-array
comb.push_back(mcl(A.at(i).getCode(),A.at(i).getName()));
// This will basically pass a sub array starting at index 'start' and going till n-1
combinations(A, comb, i + 1, n, current_k + 1, k);
}
}
else if (current_k == k){
for (int i = start; i < n; i++){
comb.at(current_k-1) = A.at(i);
for (int j = 0; j < k; j++){
sCodes += comb.at(j).getCode();
if (sNames != ""){
sNames = sNames + "," + comb.at(j).getName();
}
else{
sNames = sNames + comb.at(j).getName();
}
}
}
results.push_back(sCodes + " - " + sNames);
sCodes = 0;
sNames = "";
}
else
return;
}
int main(){
int k;
vector<mcl> A,comb;
A.push_back(mcl(1, "Light"));
A.push_back(mcl(2, "Bright"));
A.push_back(mcl(4, "Dark"));
k = 2;
combinations(A, comb, 0, A.size(), 0, k - 1);
//system("cls");
for (int i1 = 0; i1 < results.size(); i1++){
cout << results.at(i1) << endl;
}
system("pause");
return 0;
}
mcl header 和 imp 代码：
#ifndef MCL_H
#define MCL_H
#include <string>
using std::string;
class mcl{
public:
mcl(int code, string name);
int getCode();
string getName();
void setCode(int i);
void setName(string s);
private:
int cCode;
string cName;
};
#endif;
小鬼：
#include "mcl.h";
mcl::mcl(int code, string name){
cCode = code;
cName = name;
}
int mcl::getCode(){
return cCode;
}
string mcl::getName(){
return cName;
}
void mcl::setCode(int i){
cCode = i;
}
void mcl::setName(string s){
cName = s;
}
现在正题。当我尝试测试我在代码中定义的三个 mcl objects 的组合显示时，我看到了这个输出：
Bright,Dark
,Dark
Press any key to continue . . .
正如我所看到的，如果我将 k 设置为 0，每个 object 的数据都会正确显示：
1 - Light
2 - Bright
4 - Dark
Press any key to continue . . .
我认为这个问题是由创建用于显示的结果向量的 for 循环引起的，但我不确定实际问题是什么。
关于我的预期输出示例，鉴于上面代码中的硬编码元素，这就是我试图让工具输出的内容（其中粗体是基本设置，non-bolded 是组合） :
1 - 浅色
2 - 明亮
3 - 浅色、明亮
4 - 深色
5 - 浅色、深色
6 - 明亮、黑暗
7 - 亮、亮、暗
看了一会儿你的代码；并试图了解你在组合函数中找到的这部分代码引起了我的注意：
else if ( current_k == k ) {
for ( int i = start; i < n; i++ ) {
comb.at(current_k-1) = A.at(i);
for ( int j = 0; j < k; j++ ){
sCodes += comb.at(j).getCode();
if ( sNames != "" ) {
sNames = sNames + "," + comb.at(j).getName();
} else {
sNames = sNames + comb.at(j).getName();
}
}
}
results.push_back(sCodes + " - " + sNames);
sCodes = 0;
sNames = "";
} else {
return;
}
我在这里想的是你正在经历一个双 for 循环，并且在双 for 循环完成之前你不会更新你的矢量。这是你想要的吗？或者你的意思是在内部 for 循环的每次迭代后保存？ If So 那么你只需要在你的 if else 语句之后将它移动到内部 for 循环的内部，修改后的代码将如下所示：
else if ( current_k == k ) {
for ( int i = start; i < n; i++ ) {
comb.at(current_k-1) = A.at(i);
for ( int j = 0; j < k; j++ ){
sCodes += comb.at(j).getCode();
if ( sNames != "" ) {
sNames = sNames + "," + comb.at(j).getName();
} else {
sNames = sNames + comb.at(j).getName();
}
results.push_back(sCodes + " - " + sNames);
}
}
sCodes = 0;
sNames = "";
} else {
return;
}
如果这对您有任何帮助，请告诉我；不幸的是，我没有可用的时间尝试在我的 IDE 中重新创建您的代码来尝试编译、构建、运行 和调试以查看修改后版本的输出是否正确。我是从头顶视觉上做这件事的。如果我在不久的将来有空闲时间；我也许可以这样做并尝试看看我能想出什么。
因此，经过大量研究和测试后，我决定这对我的情况来说效果不佳，而且在性能方面成本太高。相反，我选择通过中介 table 的数据库内 (SQLite) 解决方案，该解决方案将以一对多关系将一个 table 中的 ID 映射到另一个 table 中的 ID。与上面示例试图通过代码处理所有代码的蛮力方法相比，更易于编码且性能非常精简。
我正在尝试创建一个工具，让我的生活更轻松，以便根据数字加法设置配置设置列表，以指示应启用哪些功能。我使用的是 2 的幂列表，从 1 到 512 (1,2,4,8,16,32,64,128,256,512)。
手动检查并创建一个列表，列出哪些值将启用哪些功能会非常耗时，因此我尝试以编程方式进行，然后将输出保存到文件中。但是，我 运行 遇到了寻找合适解决方案的问题。
我已经阅读了 Google 中关于该主题的来自 SO 和其他编码论坛的几乎所有问题，并且所有问题都涉及线性组合。这是我能够做到的，我有这个示例代码，我修改了它，然后在以下基础上构建了我的工具：
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
// A is the array that contains the numbers
// comb is an array of size k that will hold all possible combinations
// n is the size of input array
// k is 1 less than the size of combination i.e. we want to find out 4C2 k =1
// current_k is the variable that makes us simulates k loops in a recursive function
void combinations(int A[], int comb[], int start, int n, int current_k, int k){
int sum = 0;
if (k < 0)
return;
// Base case just print all the numbers 1 at a time
if (k == 0){
for (int i = 0; i < n; i++)
cout << A[i] << endl;
}
// current_k goes from 0 to k-1 and simulates a total of
// k iterations
if (current_k < k){
// if current_k = 0, and k = 3 (i.e. we need to find combinations of 4)
// then we need to leave out 3 numbers from the end because there are 3
// more nested loops
for (int i = start; i < n - (k - current_k); i++){
// Store the number in the comb array and recursively call with the remaining sub-array
comb[current_k] = A[i];
// This will basically pass a sub array starting at index 'start' and going till n-1
combinations(A, comb, i+1, n, current_k+1, k);
}
}
else if (current_k == k){
for (int i = start; i < n; i++){
comb[current_k] = A[i];
for (int j = 0; j <= k; j++){
sum += comb[j];
}
cout << sum << endl;
sum = 0;
}
}
else
return;
}
int main(){
int n;
cout << "Enter the 'n' " << endl;
cin >> n;
int *A = new int[n];
for (int i = 0; i < n; i++)
A[i] = i+1;
int k;
cout << "Enter 'k'" << endl;
cin >> k;
int *comb = new int[k];
combinations(A, comb, 0, n, 0, k-1);
system("pause");
return 0;
}
唯一的问题是我还需要 non-linear 组合。像 1+64+256 这样的东西。这是否也能够拾取这些组合？我也有一个问题，我将在 post 我的代码后解释。这是我为此使用的实际代码：
#include <iostream>
#include <vector>
#include <string>
#include "mcl.h"
using std::cout;
using std::vector;
using std::string;
using std::cin;
using std::endl;
static vector<string> results;
// A is the array that contains the numbers
// comb is an array of size k that will hold all possible combinations
// n is the size of input array
// k is 1 less than the size of combination i.e. we want to find out 4C2 k =1
// current_k is the variable that makes us simulates k loops in a recursive function
void combinations(vector<mcl> A, vector<mcl> comb, int start, int n, int current_k, int k){
string sum;
string sNames;
int sCodes = 0;
if (k < 0)
k = 0;
// Base case just print all the numbers 1 at a time
if (k == 0){
for (int i = 0; i < n; i++)
cout << A.at(i).getCode() << " - " << A.at(i).getName() << endl;
return;
}
// current_k goes from 0 to k-1 and simulates a total of
// k iterations
if (current_k < k){
// if current_k = 0, and k = 3 (i.e. we need to find combinations of 4)
// then we need to leave out 3 numbers from the end because there are 3
// more nested loops
for (int i = start; i < n - (k - current_k); i++){
// Store the number in the comb array and recursively call with the remaining sub-array
comb.push_back(mcl(A.at(i).getCode(),A.at(i).getName()));
// This will basically pass a sub array starting at index 'start' and going till n-1
combinations(A, comb, i + 1, n, current_k + 1, k);
}
}
else if (current_k == k){
for (int i = start; i < n; i++){
comb.at(current_k-1) = A.at(i);
for (int j = 0; j < k; j++){
sCodes += comb.at(j).getCode();
if (sNames != ""){
sNames = sNames + "," + comb.at(j).getName();
}
else{
sNames = sNames + comb.at(j).getName();
}
}
}
results.push_back(sCodes + " - " + sNames);
sCodes = 0;
sNames = "";
}
else
return;
}
int main(){
int k;
vector<mcl> A,comb;
A.push_back(mcl(1, "Light"));
A.push_back(mcl(2, "Bright"));
A.push_back(mcl(4, "Dark"));
k = 2;
combinations(A, comb, 0, A.size(), 0, k - 1);
//system("cls");
for (int i1 = 0; i1 < results.size(); i1++){
cout << results.at(i1) << endl;
}
system("pause");
return 0;
}
mcl header 和 imp 代码：
#ifndef MCL_H
#define MCL_H
#include <string>
using std::string;
class mcl{
public:
mcl(int code, string name);
int getCode();
string getName();
void setCode(int i);
void setName(string s);
private:
int cCode;
string cName;
};
#endif;
小鬼：
#include "mcl.h";
mcl::mcl(int code, string name){
cCode = code;
cName = name;
}
int mcl::getCode(){
return cCode;
}
string mcl::getName(){
return cName;
}
void mcl::setCode(int i){
cCode = i;
}
void mcl::setName(string s){
cName = s;
}
现在正题。当我尝试测试我在代码中定义的三个 mcl objects 的组合显示时，我看到了这个输出：
Bright,Dark
,Dark
Press any key to continue . . .
正如我所看到的，如果我将 k 设置为 0，每个 object 的数据都会正确显示：
1 - Light
2 - Bright
4 - Dark
Press any key to continue . . .
我认为这个问题是由创建用于显示的结果向量的 for 循环引起的，但我不确定实际问题是什么。
关于我的预期输出示例，鉴于上面代码中的硬编码元素，这就是我试图让工具输出的内容（其中粗体是基本设置，non-bolded 是组合） :
1 - 浅色
2 - 明亮
3 - 浅色、明亮
4 - 深色
5 - 浅色、深色
6 - 明亮、黑暗
7 - 亮、亮、暗
看了一会儿你的代码；并试图了解你在组合函数中找到的这部分代码引起了我的注意：
else if ( current_k == k ) {
for ( int i = start; i < n; i++ ) {
comb.at(current_k-1) = A.at(i);
for ( int j = 0; j < k; j++ ){
sCodes += comb.at(j).getCode();
if ( sNames != "" ) {
sNames = sNames + "," + comb.at(j).getName();
} else {
sNames = sNames + comb.at(j).getName();
}
}
}
results.push_back(sCodes + " - " + sNames);
sCodes = 0;
sNames = "";
} else {
return;
}
我在这里想的是你正在经历一个双 for 循环，并且在双 for 循环完成之前你不会更新你的矢量。这是你想要的吗？或者你的意思是在内部 for 循环的每次迭代后保存？ If So 那么你只需要在你的 if else 语句之后将它移动到内部 for 循环的内部，修改后的代码将如下所示：
else if ( current_k == k ) {
for ( int i = start; i < n; i++ ) {
comb.at(current_k-1) = A.at(i);
for ( int j = 0; j < k; j++ ){
sCodes += comb.at(j).getCode();
if ( sNames != "" ) {
sNames = sNames + "," + comb.at(j).getName();
} else {
sNames = sNames + comb.at(j).getName();
}
results.push_back(sCodes + " - " + sNames);
}
}
sCodes = 0;
sNames = "";
} else {
return;
}
如果这对您有任何帮助，请告诉我；不幸的是，我没有可用的时间尝试在我的 IDE 中重新创建您的代码来尝试编译、构建、运行 和调试以查看修改后版本的输出是否正确。我是从头顶视觉上做这件事的。如果我在不久的将来有空闲时间；我也许可以这样做并尝试看看我能想出什么。
因此，经过大量研究和测试后，我决定这对我的情况来说效果不佳，而且在性能方面成本太高。相反，我选择通过中介 table 的数据库内 (SQLite) 解决方案，该解决方案将以一对多关系将一个 table 中的 ID 映射到另一个 table 中的 ID。与上面示例试图通过代码处理所有代码的蛮力方法相比，更易于编码且性能非常精简。