cpp/recursion/prime_products Source

Viewing cpp/recursion/prime_products by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

<div>
Given a list of prime factors generate all the products that can be made from any subset of the factors and return those products in a vector

For example, given the prime factors:
<pre>
2 3 7
</pre>

there are $2^n$ subsets of these factors:

<pre>
{ {}, {2}, {3}, {7}, {2,3}, {2,7}, {3,7}, {2,3,7} }
</pre>

Which would yield the products:

<pre>
{ 1, 2, 3, 7, 6, 14, 21, 42 }
</pre>

Use recursion to help generate these products. Each recursive call should be responsible for 1 factor
and choose to either:

<ol>
<li>Include it's factor and multiply it times the current product </li>
<li>Not include it's factor and just pass long the current product </li>
</ol>

Your function should have the signature:

<pre>vector<int> allProducts(const vector<int>& primes);</pre>

But you may define a helper function if needed.

Be sure you carefully consider what is the base case?
Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

Copied from problem cpp/recursion/zero_sum (author: daveagp@gmail.com)

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

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

// add a helper function here if needed
\[
void allProductsHelper(const vector<int>& primes, vector<int>& products, int currProd, unsigned int idx)
{
if(idx == primes.size()){
products.push_back(currProd);
}
else {
// Try a product w/o this prime
allProductsHelper(primes, products, currProd, idx+1);
// Then try one with this prime
allProductsHelper(primes, products, currProd*primes[idx], idx+1);
}
}
]\

vector<int> allProducts(const vector<int>& primes)
{
\[
vector<int> products;
allProductsHelper(primes, products, 1, 0);
return products;
]\
}

void sortAndPrint(vector<int> nums){
sort(nums.begin(), nums.end());
for(unsigned int i=0; i < nums.size(); i++){
cout << nums[i] << " ";
}
cout << endl;

}

int main(int argc, char* argv[]) {
// Answers go in this vector
vector<int> products;

vector<int> primes1;
products = allProducts(primes1);
sortAndPrint(products);

products.clear();
vector<int> primes2;
primes2.push_back(2); primes2.push_back(5);
products = allProducts(primes2);
sortAndPrint(products);

products.clear();
vector<int> primes3;
primes3.push_back(2); primes3.push_back(3); primes3.push_back(7);
products = allProducts(primes3);
sortAndPrint(products);

products.clear();
vector<int> primes4;
primes4.push_back(2); primes4.push_back(3); primes4.push_back(5); primes4.push_back(11);
products = allProducts(primes4);
sortAndPrint(products);

return 0;
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	<div> Given a list of prime factors generate all the products that can be made from any subset of the factors and return those products in a vector For example, given the prime factors: <pre> 2 3 7 </pre> there are $2^n$ subsets of these factors: <pre> { {}, {2}, {3}, {7}, {2,3}, {2,7}, {3,7}, {2,3,7} } </pre> Which would yield the products: <pre> { 1, 2, 3, 7, 6, 14, 21, 42 } </pre> Use recursion to help generate these products. Each recursive call should be responsible for 1 factor and choose to either: <ol> <li>Include it's factor and multiply it times the current product </li> <li>Not include it's factor and just pass long the current product </li> </ol> Your function should have the signature: <pre>vector<int> allProducts(const vector<int>& primes);</pre> But you may define a helper function if needed. Be sure you carefully consider what is the base case?
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	Copied from problem cpp/recursion/zero_sum (author: daveagp@gmail.com) remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> #include <vector> #include <algorithm> using namespace std; // add a helper function here if needed \[ void allProductsHelper(const vector<int>& primes, vector<int>& products, int currProd, unsigned int idx) { if(idx == primes.size()){ products.push_back(currProd); } else { // Try a product w/o this prime allProductsHelper(primes, products, currProd, idx+1); // Then try one with this prime allProductsHelper(primes, products, currProdprimes[idx], idx+1); } } ]\ vector<int> allProducts(const vector<int>& primes) { \[ vector<int> products; allProductsHelper(primes, products, 1, 0); return products; ]\ } void sortAndPrint(vector<int> nums){ sort(nums.begin(), nums.end()); for(unsigned int i=0; i < nums.size(); i++){ cout << nums[i] << " "; } cout << endl; } int main(int argc, char argv[]) { // Answers go in this vector vector<int> products; vector<int> primes1; products = allProducts(primes1); sortAndPrint(products); products.clear(); vector<int> primes2; primes2.push_back(2); primes2.push_back(5); products = allProducts(primes2); sortAndPrint(products); products.clear(); vector<int> primes3; primes3.push_back(2); primes3.push_back(3); primes3.push_back(7); products = allProducts(primes3); sortAndPrint(products); products.clear(); vector<int> primes4; primes4.push_back(2); primes4.push_back(3); primes4.push_back(5); primes4.push_back(11); products = allProducts(primes4); sortAndPrint(products); return 0; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.