Last active
July 1, 2019 03:03
-
-
Save mkamilov/a0341ed921167da438b3030468abaec3 to your computer and use it in GitHub Desktop.
Tried to solve problem given in https://stackoverflow.com/questions/53939655/generating-in-order-constrained-sets
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <set> | |
#include <unordered_map> | |
#include <queue> | |
#include <time.h> | |
#include <bitset> | |
#include <algorithm> | |
#include <functional> | |
using namespace std; | |
int TC = 5; | |
int MAX_CATEGORY = 32; | |
int MIN_ITEMS = 1000; | |
int MAX_ITEMS = 1000; | |
int MAX_PRICE = 10; | |
int MIN_PRICE = 2; | |
int MAX_RAND_VALUE = 100; | |
int MAX_ITEM_ID = 10000; | |
int PRICE_TAG = 50; | |
int TOP_X = 100; | |
class Item { | |
public: | |
// using single unsigned int bitwise check sets | |
unsigned int category; | |
int name; | |
int value; | |
int price; | |
Item(unsigned int c, int i, int v, int p) : category(c), name(i), value(v), price(p) {} | |
void print() { | |
cout << "name=" << name << " value=" << value << " price=" << price << " category="; | |
int i = 0; | |
while (category) { | |
if (category & 1) { | |
cout << i << ","; | |
} | |
category = category >> 1; | |
i++; | |
} | |
cout << endl; | |
} | |
friend bool operator== (const Item &n1, const Item &n2); | |
}; | |
class ItemSet | |
{ | |
public: | |
set<Item> items; | |
int sum; | |
}; | |
bool operator== (const Item& item1, const Item& item2) | |
{ | |
return (item1.category == item2.category) && | |
(item1.name == item2.name) && | |
(item1.price == item2.price) && | |
(item1.value == item2.value); | |
} | |
bool operator<(const ItemSet& item1, const ItemSet& item2) { | |
return item1.sum < item2.sum; | |
} | |
bool operator<(const Item& item1, const Item& item2) { | |
if (item1.value == item2.value) { | |
if (item1.price == item2.price) { | |
return item1.name < item2.name; | |
} | |
return item1.price > item2.price; | |
} | |
return item1.value < item2.value; | |
} | |
bool operator>(const Item& item1, const Item& item2) { | |
if (item1.value == item2.value) { | |
return item1.price < item2.price; | |
if (item1.price == item2.price) { | |
return item1.name > item2.name; | |
} | |
} | |
return item1.value > item2.value; | |
} | |
priority_queue<ItemSet> output; | |
vector<Item> generateTestItem() | |
{ | |
int items = MIN_ITEMS+rand() % MAX_ITEMS; // amount of items | |
srand(time(NULL)); | |
vector<Item> v; | |
set<int> itemDuplicateTester; | |
for (int j = 0; j < items; ++j) { | |
int catSize = rand() % 10; // amount of categories for each item | |
unsigned int cats = 0; | |
for (int c = 0; c <= catSize; ++c) { | |
int r = rand() % MAX_CATEGORY; | |
cats |= 1 << r; | |
} | |
int itemId = rand() % MAX_ITEM_ID; | |
int value = rand() % MAX_RAND_VALUE; | |
int price = MIN_PRICE + rand() % MAX_PRICE; | |
// make sure generated item is unique with itemDuplicateTester | |
if (itemDuplicateTester.find(itemId) == itemDuplicateTester.end()) { | |
v.push_back(Item(cats, itemId, value, price)); | |
itemDuplicateTester.insert(itemId); | |
//v.back().print(); | |
} | |
} | |
return v; | |
} | |
void addOutput(set<Item>& currentItems) | |
{ | |
ItemSet myset; | |
int setsum = 0; | |
for (auto a : currentItems) { | |
setsum += a.value; | |
} | |
myset.items = currentItems; | |
myset.sum = setsum; | |
output.push(myset); | |
} | |
void helper(vector<Item>& input, set<Item>& currentItems, unsigned int currentCats, int sum, int index) | |
{ | |
if (index == input.size()) { | |
// Need to check if currentItems matches the blueprint | |
// if yes, then call addOutput | |
addOutput(currentItems); | |
return; | |
} | |
if (output.size() >= TOP_X) { | |
return; | |
} | |
if (sum + input[index].price < PRICE_TAG) { | |
// this condition needs to be changed | |
// we need to have category checker method which would return true if we are ok to include | |
// input[index] item's category as per blueprint | |
if ((input[index].category & currentCats) == 0) { | |
currentItems.insert(input[index]); | |
helper(input, currentItems, currentCats | input[index].category, sum + input[index].price, index + 1); | |
} | |
} else { | |
// Need to check if currentItems matches the blueprint | |
// if yes, then call addOutput | |
addOutput(currentItems); | |
return; | |
} | |
if (currentItems.find(input[index]) != currentItems.end()) { | |
currentItems.erase(input[index]); | |
} | |
helper(input, currentItems, currentCats, sum, index + 1); | |
return; | |
} | |
void getTopItems(vector<Item>& items) | |
{ | |
set<Item> myset; | |
helper(items, myset, 0, 0, 0); | |
} | |
int main() | |
{ | |
for (int i = 0; i < TC; ++i) { | |
vector<Item> v = generateTestItem(); | |
cout << "generated items : " << v.size() << endl; | |
sort(v.begin(), v.end(), greater<Item>()); | |
getTopItems(v); | |
cout << "got ans " << output.size() << endl; | |
int j = 0; | |
while (output.empty() == false) { | |
set<Item> myset = output.top().items; | |
output.pop(); | |
int priceSum = 0, valueSum = 0; | |
for (auto a : myset) { | |
priceSum += a.price; | |
valueSum += a.value; | |
} | |
j++; | |
cout << "set size=" << myset.size() << " priceSum= " << priceSum << " valueSum = " << valueSum << endl; | |
} | |
} | |
return 0; | |
} |
codinghaven
commented
Jun 28, 2019
via email
I will make a video showing why simple descent on a sorted list isn't
optimal.
In respect to your question, I have delved in this problem for a while now
and haven't found that this should be necessary at all. We could simply use
an unordered set and check for duplicates, which is O(1) time. There are
many efficient ways to deal with duplicate items, the harder problem is how
to efficently make sure that duplicate sets aren't generated which can
happen if we have categories that share other categories, like Food and
Cheese.
I am so close to a dynamic solution and it consequentially takes care of
duplicate sets due to the nature of the algorithm.
But if you have any insight please by all means let me know.
Hope to post a video depicting an example soon, thanks!
…On Fri, Jun 28, 2019, 1:14 AM Miradham Kamilov ***@***.***> wrote:
I think I can understand you, though having some real examples would help
more.
Do you think if we change input items so that they have only single
category, we can achieve our goal easier? For ex if cheese has 2 cats: Food
and Diary, we can separate it and have 2 cheeses, one with cat food and one
with cat diary. When we build up our output sets, we make sure that items
with same names does not go inside single set. And, of course, we will be
following blueprint for output.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<https://gist.github.com/a0341ed921167da438b3030468abaec3?email_source=notifications&email_token=AC5GJTJZVGGDNFKRLTL7273P4WMZRA5CNFSM4H3VRTZ2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAFUN26#gistcomment-2956207>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AC5GJTPXJKSM5ZVY5GVGDJDP4WMZRANCNFSM4H3VRTZQ>
.
Here is the example showing why your solution isn't optimal.
https://awwapp.com/b/uuyfktgxv/
Here is a video going through the example:
https://drive.google.com/open?id=1MSMHb16K5D17ul1LBMCwlRkcC93uokQF
I have figured out a solution I am writing the code now will notify you when done.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment