Suppose I have an array of numbers A = {1,2,3,...,n}

It is necessary to generate all the subsets of a given array of capacity m

Say A = {1,2,3,4}, m = 3

Then the subsets: {1,2,3} {2,3,4} {1,3,4} {1,2,4}

How to implement such an algorithm in C # or C ++?

    2 answers 2

    In C ++ 11:

     template <typename T> class SubSeq { public: class Index { public: Index(size_t seq_size, size_t subseq_size) : ss(seq_size), s(subseq_size), data() { data.reserve(s + 1); for (size_t i = 0; i < s; ++i) data.push_back(i); data.push_back(ss); } bool next() { return next(s-1); } bool next(size_t i) { data[i]++; for (size_t j = i + 1; j < s; ++j) data[j] = data[j - 1] + 1; if (data[s - 1] >= data[s]) { if (i > 0) return next(i-1); else return false; } else { return true; } } size_t operator[] (size_t i) { return data[i]; } private: size_t ss, s; std::vector<size_t> data; }; SubSeq(const std::vector<T>& data, size_t subseq_size) : seq_size(data.size()), subseq_size(subseq_size), data(data), index(data.size(), subseq_size), ended(subseq_size > data.size() || subseq_size == 0) {} std::vector<T> next() { std::vector<T> v; v.reserve(subseq_size); for (size_t i = 0; i < subseq_size; ++i) v.push_back(data[index[i]]); ended = !index.next(); return v; } bool end() { return ended; } void start() { index = Index(seq_size, subseq_size); ended = subseq_size > seq_size || subseq_size == 0; } private: size_t seq_size, subseq_size; std::vector<T> data; Index index; bool ended; };

    Using:

     std::vector<int> v = {1, 2, 3, 4}; SubSeq<int> ss(v, 3); while (! ss.end()) { std::vector<int> s = ss.next(); }

    in s there will be vectors {1,2,3}, {1,2,4}, ..., {2,3,4}

    Just had the ready code.

      C #

       public Array ArraySub(int[] param) { int[] a = new int[] {1,2,3,4}; //В метод можно передать данные извне, не очень красиво, но работает if (param.Any()) { a = param; } //шаг выборки int step = 3; int lenght = step; int i = 0; //Здесь будут ссылочные данные ArraySegment, содержимое меняется вместе с родительским массивом Array subA = new Array[] {}; //А это новый массив, с скопированными данными Array[] subClone = new Array[] {}; while (lenght <= a.Length) { subA.SetValue(new ArraySegment<int>(a, lenght-step, step), i); subClone.SetValue(a.Skip(lenght-step).Take(step).ToArray(),i); i++; lenght++; } //возвращать можем как первоначальный массив так и subA или subClone return a; }

      and read about arrays in msdn.