1

我想生成以下序列：

set S = {1,2,3}
op = {{1,2},{1,3},{2,3}}

set S = {1,2,3,4}
op = {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

set S = {1,2,3,4,5}
op = {{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}

一般来说，给定一组 n 个数字，我必须找到 (n-1) 个数字的所有可能子集，并限制它们按字母顺序排列（数字按顺序排列）。

是否有任何算法或方法来解决特定问题？我知道我们可以使用递归来生成更小的子集。

4

5 回答 5

2

只有n这样的子集；每个都n从原始集合中删除了一个原始数字。因此，对集合进行排序，并为每个数字创建一个集合，该集合是删除该数字的原始集合。

一个可能的警告是，如果原始集合中有重复的数字，您将只有与原始集合中唯一数字一样多的子集，因此可能比n这种情况下少。

于 2013-02-23T07:16:00.293 回答
2

某些语言内置了此功能。例如 Python 的itertools.combinations()方法. 在你的情况下：

>>> import itertools
>>> l = [1,2,3,4]
>>> combinations = itertools.combinations(l, len(l) -  1) #for the list of numbers l, for sublists with a length 1 less than l's length
>>> for comb in combinations:
...     print comb
...
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)
>>>

但是，如果您想自己实现它，上面的链接可能仍然有用，因为它显示了等效的代码。您可以使用此代码以任何语言制作自己的实现。

于 2013-02-23T07:16:55.673 回答
2

想一想

  • 如何生成集合 1..N
  • 如何识别要从每个集合中删除的数字n (n: N .. 1)

从 1..N 生成/打印一个集合

print "{"
for i=1 to N
  if (i > 1) print ","
  print i
end
print "}"

如何创建一个从 N 到 1中选择n的循环

for j=N to 1 
  ...
end

使用最后一个循环作为上面循环的包装器 - 并且在上面的循环中测试当前选择的数字j是否等于i并且在这种情况下不打印它。

为了好玩，一个不假装优化的 Perl 实现:-)

$N = 5;

sub rec {
  my($j,$i,@a) = @_;
  if ($j > 0) {
    while (++$i <= $N) { push(@a,$i) if ($i != $j); }
    print('{' . join(',', @a) . "}\n");
    &rec($j-1);
  }
}

&rec($N);

或者这个，（也许）更传统

for ($i=$N ; $i>0 ; $i--) {
  @a = ();
  for (1..$N) { push(@a,$_) if ($i != $_); }
  print('{' . join(',', @a) . "}\n");
}
于 2013-02-23T12:22:16.767 回答
2

这应该很简单。让 arr 有排序的集合， n 是元素的数量：

int arr[100];
int n;
printf("{");
for (int i = n - 1; i >= 0; i--){
    printf("{");
    for (int j = 0; j < n; j++) {
        if (i == j) {
            continue;
        }
        printf("%d, ", arr[j]);
    }
    printf("}, ");
}
printf("}\n");

上面打印了一些额外的逗号，您可以自己过滤掉它们。

于 2013-02-23T11:47:23.343 回答
1

在 Haskell 中，你可以这样做：

import Data.List

combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

subsets set =  combinations (length set - 1) (sort set)


哈斯克尔，简要地说：

_                                   =>    anyting
[]                                  =>    empty list
a = 1; as = [2,3]                   =>    a:as = [1,2,3]
[a:b | a <- [1], b <- [[2],[3]]]    =>    [[1,2],[1,3]]
tails [1,2,3]                       =>    [[1,2,3],[2,3],[3],[]]


例如，“组合 2 [1,2,3]”：

tails xs = [[1,2,3],[2,3],[3],[]]

[1,2,3]   =>   y = 1; ys = [[2],[3]]    =>    [1,2],[1,3]
[2,3]     =>   y = 2; ys = [[3]]        =>    [2,3]
[3]       =>   y = 3; ys = NULL         =>    []

Result [[1,2],[1,3],[2,3]]
于 2013-02-23T14:58:04.210 回答