比特掩码的递归关系 [英] Recurrence relation for bitmasking

问题描述

基本上我试图计算下面解决方案的时间复杂度，我从[Bit masking cap problem] [1]中解决了这个问题并且理解得很好但是当递归进入循环时无法计算时间复杂度/>
甚至我的教授都没有这样做怎么办？

我怎么能写这个的递归关系？



*** BIT MASKING ***





有100种不同类型的帽子，每种帽子都有1到100的唯一ID此外，还有'n'人各自拥有可变数量的大写字母的集合。有一天，所有这些人都决定参加一个戴着帽子的派对，但看起来很独特，他们认为他们都不会戴同样的帽子。因此，请计算总数或方式，使其中没有人佩戴相同类型的上限。



约束条件：1< = n< = 10例如：



我尝试过：

Basically I was trying to calculate the time complexity of below solution ,I took this problem from [Bit masking cap problem][1] and understand it very well But unable to calculate the time complexity as recursion is going inside loop
Even my professor didn't get this how to do it?
How can i write recurrence relation for this?

***BIT MASKING***


There are 100 different types of caps each having a unique id from 1 to 100. Also, there are ‘n’ persons each having a collection of a variable number of caps. One day all of these persons decide to go in a party wearing a cap but to look unique they decided that none of them will wear the same type of cap. So, count the total number of arrangements or ways such that none of them is wearing the same type of cap.

Constraints: 1 <= n <= 10 Example:

What I have tried:

// C++ program to find number of ways to wear hats
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;

// capList[i]'th vector contains the list of persons having a cap with id i
// id is between 1 to 100 so we declared an array of 101 vectors as indexing
// starts from 0.
vector<int> capList[101];

// dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that
// how many and which persons are wearing cap. j denotes the first j caps
// used. So, dp[i][j] tells the number ways we assign j caps to mask i
// such that none of them wears the same cap
int dp[1025][101];

// This is used for base case, it has all the N bits set
// so, it tells whether all N persons are wearing a cap.
int allmask;

// Mask is the set of persons, i is cap-id (OR the
// number of caps processed starting from first cap).
long long int countWaysUtil(int mask, int i)
{
    // If all persons are wearing a cap so we
    // are done and this is one way so return 1
    if (mask == allmask) return 1;

    // If not everyone is wearing a cap and also there are no more
    // caps left to process, so there is no way, thus return 0;
    if (i > 100) return 0;

    // If we already have solved this subproblem, return the answer.
    if (dp[mask][i] != -1) return dp[mask][i];

    // Ways, when we don't include this cap in our arrangement
    // or solution set.
    long long int ways = countWaysUtil(mask, i+1);

    // size is the total number of persons having cap with id i.
    int size = capList[i].size();

    // So, assign one by one ith cap to all the possible persons
    // and recur for remaining caps.
    for (int j = 0; j < size; j++)
    {
        // if person capList[i][j] is already wearing a cap so continue as
        // we cannot assign him this cap
        if (mask & (1 << capList[i][j])) continue;

        // Else assign him this cap and recur for remaining caps with
        // new updated mask vector
        else ways += countWaysUtil(mask | (1 << capList[i][j]), i+1);
        ways %= MOD;
    }

    // Save the result and return it.
    return dp[mask][i] = ways;
}

// Reads n lines from standard input for current test case
void countWays(int n)
{
    //----------- READ INPUT --------------------------
    string temp, str;
    int x;
    getline(cin, str); // to get rid of newline character
    for (int i=0; i<n; i++)
    {
        getline(cin, str);
        stringstream ss(str);

        // while there are words in the streamobject ss
        while (ss >> temp)
        {
            stringstream s;
            s << temp;
            s >> x;

            // add the ith person in the list of cap if with id x
            capList[x].push_back(i);
        }
    }
    //----------------------------------------------------

    // All mask is used to check whether all persons
    // are included or not, set all n bits as 1
    allmask = (1 << n) - 1;

    // Initialize all entries in dp as -1
    memset(dp, -1, sizeof dp);

    // Call recursive function count ways
    cout << countWaysUtil(0, 1) << endl;
}

// Driver Program
int main()
{
    int n; // number of persons in every test case
    cin >> n;
    countWays(n);
    return 0;
}

推荐答案

我在dp中看到你应该改变索引顺序以改善的问题清晰但头部的标记是神秘的。为什么不是dp（坏名称）一个int数组，索引是学生，值是head。 MOD的使用还不清楚，所以你应该对它进行评论。



想想你的数据设计，也许有些课程会很方便。



当学生可以有不同的头数时，有些人可能只有一个（或两个）以及当这些数字相同时。所以请注意不可解决的案例。



尝试一些测试数据来查找代码中的问题。

I see the problem in dp where you should change the order of the indices to improve clarity but the flagging of the heads is mysterious. Why isnt dp (bad name) a int array which the index is the student and the value is the head. The usage of MOD is unclear, so you should comment it.

Think about your data design, maybe some classes would be handy.

When student can have different count of heads, so some may have only one (or two) and what when these have the same numbers. So take care about nonsolvable cases.

Try some test data to find the problems in your code.

这篇关于比特掩码的递归关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！