f******n
发帖数: 640 | 1 9.4: wtrit a method to return all subsets of a set
想了好久，也没弄出来了 真的是很弱啊
请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
点啊？
小弟先谢过了 |
a********x
发帖数: 1502 | 2 我觉得是用recurrsion来写。见斯坦福大学programming abstraction里面的某一节
【在 f******n 的大作中提到】
: 9.4: wtrit a method to return all subsets of a set
: 想了好久，也没弄出来了 真的是很弱啊
: 请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
: 点啊？
: 小弟先谢过了
|
a*******y
发帖数: 1040 | 3 现场写一个吧：
void Subset(int A[],int n)
{
int number = 1<
for (int i = 0;i < number; i++)
{
int temp = i;
int* ele = A;
cout << "{"
while (temp > 0)
{
if (temp&0x01)
count <<*A;
temp >>=1;
++ele;
}
cout <<"} "
}
} |
l*****a
发帖数: 14598 | 4 overflow
【在 a*******y 的大作中提到】
: 现场写一个吧：
: void Subset(int A[],int n)
: {
: int number = 1<: for (int i = 0;i < number; i++)
: {
: int temp = i;
: int* ele = A;
: cout << "{"
: while (temp > 0)
|
l*****a
发帖数: 14598 | 5 i assume that u want to write
cout<<*ele
【在 a*******y 的大作中提到】
: 现场写一个吧：
: void Subset(int A[],int n)
: {
: int number = 1<: for (int i = 0;i < number; i++)
: {
: int temp = i;
: int* ele = A;
: cout << "{"
: while (temp > 0)
|
a*******y
发帖数: 1040 | 6 oops,你好聪明耶，这都被你看出来了
【在 l*****a 的大作中提到】
: i assume that u want to write
: cout<<*ele
|
i*********n
发帖数: 58 | 7 Pseudocode and implementation needs to be optimized:
set PowerSet(set input)
if (input.empty())
return set.insert(EmptySet);
else
e = input.first();
input.removeFirst();
input = PowerSet(input);
for (iter = input.second(); iter != input.end(); ++iter)
set.insert(SetUnion(e, *iter));
return SetUnion(set, input);
|
a*******y
发帖数: 1040 | 8 change to unsigned long,
if you still say overflow, I can do nothing but fule you.
【在 l*****a 的大作中提到】
: overflow
|
g**w
发帖数: 969 | 9 想了一个non recursion
set.add(EmptySet)
foreach (item in Set)
{
tmpset = empty;
foreach (s in set)
{
news = s.clone();
news.addelement(item);
tmpset.add(news);
}
set.addset(tmpset);
} |
T******n
发帖数: 11 | 10 我用vector表示set，结果是一个vector的vector。不用recursion。
1. 把empty set加入结果；
2. 遍历set里的元素，每碰到一个都是把之前的结果复制一遍，然后把set里的新元素
加入，然后加入结果中；
vector > powerSet(vector& set) {
vector > subsets;
vector emptySet;
subsets.push_back(emptySet);
for(int i = 0; i < set.size(); i++) {
vector > add = subsets;
for(int j = 0; j < add.size(); j++) {
add[j].push_back(set[i]);
subsets.push_back(add[j]);
}
}
return subsets;
} |
C***U
发帖数: 2406 | 11 那本书上已经提醒你了 如果出现all这种词就要用recursion。
【在 f******n 的大作中提到】
: 9.4: wtrit a method to return all subsets of a set
: 想了好久，也没弄出来了 真的是很弱啊
: 请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
: 点啊？
: 小弟先谢过了
|
t****a
发帖数: 1212 | 12 初学者，给一个lisp的解：
(defn all-subset [s]
(if (= (count s) 1)
[s]
(let [fst (first s)
rst (rest s)
rst-sub (all-subset rst)
new-sub (map #(cons fst %) rst-sub)
all-sub (concat [[fst]] rst-sub new-sub)]
all-sub)))
(all-subset [1 2 3 4 5])
; ([1] [2] [3] [4] (5) (4 5) (3 4) (3 5) (3 4 5) (2 3) (2 4) (2 5) (2 4 5) (
2 3 4) (2 3 5) (2 3 4 5) (1 2) (1 3) (1 4) (1 5) (1 4 5) (1 3 4) (1 3 5) (1
3 4 5) (1 2 3) (1 2 4) (1 2 5) (1 2 4 5) (1 2 3 4) (1 2 3 5) (1 2 3 4 5))
【在 f******n 的大作中提到】
: 9.4: wtrit a method to return all subsets of a set
: 想了好久，也没弄出来了 真的是很弱啊
: 请教各位能不能给一些用C++解决的思路呢，例如应该用哪个data structure比较好一
: 点啊？
: 小弟先谢过了
|
d****h
发帖数: 21 | 13 初学者，给一个haskell解法：
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = (map (x:) (subsets xs))++(subsets xs) |
