debugging C++中将组合分离为向量的问题

am46iovg  于 2023-06-23  发布在  其他
关注(0)|答案(2)|浏览(110)

我有一个由16对符号和颜色组成的向量,其中有4种不同的颜色和4种不同的符号。我需要将这些组合分成4个不同的向量,条件如下:
符号不能与同一矢量中的另一个符号具有相同的颜色。一种颜色不能与同一矢量中的另一种颜色具有相同的符号。符号和颜色的组合只能在4个矢量中使用一次。我尝试过在C++中实现分离逻辑,但我遇到了一个问题,有时,一些组合没有被分配给任何向量,即使应该可以分配它们。
我已经尝试过使用random_shuffle随机打乱组合,并检查了逻辑的有效性。然而,问题仍然存在,我无法确定原因。
有人能帮我找出问题所在,并提供解决方案,以确保所有组合都分配给满足给定条件的向量吗?我感谢任何指导或建议。谢谢你!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<char> symbols = {'&', '#', '%', '$'};
vector<char> colors = {'R', 'G', 'B', 'Y'};
vector<pair<char, char>> combinations;

void separateVectors() {
    // Shuffle the combinations randomly
    srand(time(0));
    random_shuffle(combinations.begin(), combinations.end());

    vector<vector<pair<char, char>>> vectors(4); // Store the four separate vectors

    for (const auto& combination : combinations) {
        bool assigned = false; // Flag to indicate if the combination has been assigned

        // Iterate over the vectors to find a suitable one for the current combination
        for (int i = 0; i < 4; i++) {
            bool valid = true;

            // Check if the symbol or color already exists in the current vector
            for (const auto& pair : vectors[i]) {
                if (pair.first == combination.first || pair.second == combination.second) {
                    valid = false;
                    break;
                }
            }

            // If the combination satisfies the conditions, add it to the current vector and update the flag
            if (valid) {
                vectors[i].push_back(combination);
                assigned = true;
                break;
            }
        }

        // If the combination couldn't be assigned to any vector, print a warning
        if (!assigned) {
            cout << "Warning: Combination (" << combination.first << ", " << combination.second << ") couldn't be assigned." << endl;
        }
    }

    // Print the four separate vectors
    for (int i = 0; i < 4; i++) {
        cout << "Vector " << i << endl;
        for (const auto& pair : vectors[i]) {
            cout << "Symbol: " << pair.first << " Color: " << pair.second << endl;
        }
        cout << endl;
    }
}

int main() {
    // Generate all possible combinations
    for (const auto& symbol : symbols) {
        for (const auto& color : colors) {
            combinations.push_back(make_pair(symbol, color));
        }
    }

    separateVectors();

    return 0;
}

预期输出:预期的输出应该是四个单独的向量,每个向量包含符号和颜色的四种组合,满足给定的条件。示例:

Vector 0
Symbol: # Color: Y
Symbol: $ Color: R
Symbol: & Color: B
Symbol: % Color: G

Vector 1
Symbol: # Color: R
Symbol: & Color: Y
Symbol: % Color: B
Symbol: $ Color: G

Vector 2
Symbol: # Color: G
Symbol: % Color: Y
Symbol: & Color: R
Symbol: $ Color: B

Vector 3
Symbol: & Color: G
Symbol: # Color: B
Symbol: $ Color: Y
Symbol: % Color: R

电流输出:当前的输出没有将某些组合分配给任何向量,即使应该可以分配它们。示例:

Warning: Combination ($, Y) couldn't be assigned.
Warning: Combination (&, B) couldn't be assigned.
Vector 0
Symbol: # Color: G
Symbol: $ Color: B
Symbol: % Color: R
Symbol: & Color: Y

Vector 1
Symbol: # Color: B
Symbol: & Color: G
Symbol: % Color: Y
Symbol: $ Color: R

Vector 2
Symbol: % Color: G
Symbol: & Color: R
Symbol: # Color: Y

Vector 3
Symbol: % Color: B
Symbol: $ Color: G
Symbol: # Color: R

附加说明:
我已经验证了检查有效性和将组合分配给向量的逻辑,但问题仍然存在。这个问题只发生在50%的时间,大多数时间,组合从向量2和3中丢失,很少从0和1中丢失。有时有多达5个组合没有分配,但大多数时候只有一两个。
我将非常感谢任何见解,建议,或解决这个问题的解决方案。提前感谢您的帮助!

ut6juiuv

ut6juiuv1#

问题是你的算法是贪婪的,导致你陷入局部极小(死胡同)。在结果中,$Y不能放入任何桶中,因为每个桶都有$符号或Y颜色。但是,如果你看一下桶0,你会注意到它包含了$B,它 * 可以 * 放在桶2中。如果你也将& Y移动到桶3中,你实际上可以将$Y放置到桶0中。

  • 您可以尝试构建一个 * 增强逻辑 *,可以识别这些情况并移动已经放置的项目(对于一个想法,请看:Diniz或Dijkstra)。
  • 或者,您可以使用随机算法,随机尝试将项目移动到未满的桶中,以便为不可放置的项目腾出空间。你可以在只剩下无法放置的项目时启动这个算法(对于一个想法,请看一下:模拟退火)。

Here是一个以非常基本的方式模拟模拟退火的例子。它在平均17轮内收敛到完美解:

std::mt19937 gen(0);
  while (true) {
    greedy(combinations, buckets); // straightforward greedy algorithm
    if (combinations.empty()) break;
    extract_random(gen, combinations, buckets);
  }
inline bool extract_random(std::mt19937& gen, std::vector<Item>& items,
                           std::array<std::vector<Item>, 4>& buckets) {
  std::shuffle(begin(buckets), end(buckets), gen);
  for (auto& b : buckets) std::shuffle(begin(b), end(b), gen);
  auto const i = std::uniform_int_distribution<std::size_t>(0, 3)(gen);
  if (buckets[i].empty()) return false;
  auto const k =
      std::uniform_int_distribution<std::size_t>(0, buckets[i].size() - 1)(gen);
  items.push_back(std::exchange(buckets[i][k], buckets[i].back()));
  buckets[i].pop_back();
  return true;
}
46scxncf

46scxncf2#

为什么你不简单地循环排列颜色(比如说)并输出一个显式生成的集合,而不是依赖于随机化(正如已经指出的那样)导致死胡同。

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

//----------------------------------------------------------------------

vector< vector<string> > getCombinations( string symbols, string colours )
{
   int N = symbols.size();
   vector< vector<string> > result;

   for ( int c = 0; c < N; c++ )
   {
      vector<string> V( N );
      for ( int i = 0; i < N; i++ ) V[i] = V[i] + symbols[i] + colours[i];
      result.push_back( V );
      colours = colours.substr( 1 ) + colours[0];     // cyclic rotation
   }
   return result;
}

//----------------------------------------------------------------------

int main()
{
   vector< vector<string> > combinations = getCombinations( "&#%$", "RGBY" );
   for ( int i = 0; i < combinations.size(); i++ )
   {
      cout << "\nVector " << i << '\n';
      for ( string s : combinations[i] ) cout << "Symbol: " << s[0] << " Colour: " << s[1] << '\n';
   }
}

输出:

Vector 0
Symbol: & Colour: R
Symbol: # Colour: G
Symbol: % Colour: B
Symbol: $ Colour: Y

Vector 1
Symbol: & Colour: G
Symbol: # Colour: B
Symbol: % Colour: Y
Symbol: $ Colour: R

Vector 2
Symbol: & Colour: B
Symbol: # Colour: Y
Symbol: % Colour: R
Symbol: $ Colour: G

Vector 3
Symbol: & Colour: Y
Symbol: # Colour: R
Symbol: % Colour: G
Symbol: $ Colour: B

相关问题