Вопросы Теги

Как найти все возможные подмножества данного массива?

Хорошо, после прочтения некоторого теоретического материала и «мышления дедукции» (c), я нашел решение:

  1. Я создал папку /usr/local/lib/ueye_olga
  2. Я скопировал все необходимые библиотеки из корня проекта lib и его подпапок в ueye_olga, см. вывод ниже.
  3. Я удалил ненужные файлы и заменил их ссылками (см. Пояснения ниже).
  4. Я создал /etc/ld.so.conf.d/ueye_olga.conf with path to the / usr / local / lib / ueye_olga`, см. Ниже.
  5. Я сделал sudo ldconfig
  6. Я проверил, что libueye_stream.so связан правильно (см. Ниже)
  7. Мне нужно было переместить libueye_stream.so, и его папка ссылок вверх, я не не знаю почему, см. ошибку ниже.
  8. Снова sudo ldconfig
  9. make работает правильно

/ usr / local / lib / ueye_olga` : 

olga@olga-MS-7758:/usr/local/lib$ ls -la ueye_olga/
total 15984
drwxr-xr-x 2 root root     4096 мар 22 15:13 .
drwxr-xr-x 7 root root    12288 мар 22 15:27 ..
lrwxrwxrwx 1 root root       16 мар 22 15:02 libavcodec.so -> libavcodec.so.56
lrwxrwxrwx 1 root root       23 мар 22 15:02 libavcodec.so.56 -> libavcodec.so.56.60.100
-rwxr-xr-x 1 root root 12294344 мар 22 14:35 libavcodec.so.56.60.100
lrwxrwxrwx 1 root root       17 мар 22 15:04 libavdevice.so -> libavdevice.so.56
lrwxrwxrwx 1 root root       23 мар 22 15:04 libavdevice.so.56 -> libavdevice.so.56.4.100
-rwxr-xr-x 1 root root    62384 мар 22 14:35 libavdevice.so.56.4.100
lrwxrwxrwx 1 root root       16 мар 22 15:05 libavfilter.so -> libavfilter.so.5
lrwxrwxrwx 1 root root       23 мар 22 15:04 libavfilter.so.5 -> libavfilter.so.5.40.101
-rwxr-xr-x 1 root root   129104 мар 22 14:35 libavfilter.so.5.40.101
lrwxrwxrwx 1 root root       17 мар 22 15:06 libavformat.so -> libavformat.so.56
lrwxrwxrwx 1 root root       24 мар 22 15:06 libavformat.so.56 -> libavformat.so.56.40.101
-rwxr-xr-x 1 root root  1152424 мар 22 14:35 libavformat.so.56.40.101
lrwxrwxrwx 1 root root       15 мар 22 15:07 libavutil.so -> libavutil.so.54
lrwxrwxrwx 1 root root       22 мар 22 15:07 libavutil.so.54 -> libavutil.so.54.31.100
-rwxr-xr-x 1 root root   336088 мар 22 14:35 libavutil.so.54.31.100
lrwxrwxrwx 1 root root       29 мар 22 15:11 libBasicUsageEnvironment.so -> libBasicUsageEnvironment.so.1
lrwxrwxrwx 1 root root       33 мар 22 15:10 libBasicUsageEnvironment.so.1 -> libBasicUsageEnvironment.so.1.0.0
-rw-r--r-- 1 root root    55839 мар 22 14:36 libBasicUsageEnvironment.so.1.0.0
lrwxrwxrwx 1 root root       17 мар 22 15:11 libgroupsock.so -> libgroupsock.so.8
lrwxrwxrwx 1 root root       21 мар 22 15:11 libgroupsock.so.8 -> libgroupsock.so.8.1.0
-rw-r--r-- 1 root root    74323 мар 22 14:36 libgroupsock.so.8.1.0
lrwxrwxrwx 1 root root       18 мар 22 15:12 libliveMedia.so -> libliveMedia.so.52
lrwxrwxrwx 1 root root       22 мар 22 15:12 libliveMedia.so.52 -> libliveMedia.so.52.0.4
-rw-r--r-- 1 root root  1395586 мар 22 14:36 libliveMedia.so.52.0.4
lrwxrwxrwx 1 root root       18 мар 22 15:12 libswresample.so -> libswresample.so.1
lrwxrwxrwx 1 root root       24 мар 22 15:12 libswresample.so.1 -> libswresample.so.1.2.101
-rwxr-xr-x 1 root root   108008 мар 22 14:35 libswresample.so.1.2.101
lrwxrwxrwx 1 root root       15 мар 22 15:13 libswscale.so -> libswscale.so.3
lrwxrwxrwx 1 root root       21 мар 22 15:13 libswscale.so.3 -> libswscale.so.3.1.101
-rwxr-xr-x 1 root root   549048 мар 22 14:35 libswscale.so.3.1.101
lrwxrwxrwx 1 root root       19 мар 22 14:12 libueye_stream.so -> libueye_stream.so.2
lrwxrwxrwx 1 root root       21 мар 22 14:11 libueye_stream.so.2 -> libueye_stream.so.2.0
-rwxr-xr-x 1 root root   151018 мар 22 14:29 libueye_stream.so.2.0
lrwxrwxrwx 1 root root       24 мар 22 15:13 libUsageEnvironment.so -> libUsageEnvironment.so.3
lrwxrwxrwx 1 root root       28 мар 22 15:13 libUsageEnvironment.so.3 -> libUsageEnvironment.so.3.1.0
-rw-r--r-- 1 root root    15809 мар 22 14:36 libUsageEnvironment.so.3.1.0

[ 1131] Удаление ненужных файлов :

Если вы не создадите программные ссылки, вы получите сообщение об ошибке, например:

/sbin/ldconfig.real: / usr / local / lib / ueye_olga / libavcodec.so.56 не является символической ссылкой

blockquote>

Причина:

Как обычно для библиотечных модулей, можно установить libstdc как одна из нескольких версий. Обычно устанавливается только одна версия, а другие возможные версии представлены в виде символической ссылки на установленную версию. Символическая ссылка - это другое имя, указывающее на установленный модуль. Например, у меня установлен /usr/lib/libstdc++.so.6.0.10. У меня также есть /usr/liblibstdc++.so.6 в качестве символической ссылки, указывающей на /usr/lib/libstdc++.so.6.0.10, так что вы можете получить доступ к libstdc ++ под любым именем.

blockquote>

Взято из здесь .

/etc/ld.so.conf.d/ueye_olga.conf : 

olga@olga-MS-7758:/usr/local/lib$ cat /etc/ld.so.conf.d/ueye_olga.conf
/usr/local/lib/ueye_olga

Связанные ссылки ueye_stream : 

olga@olga-MS-7758:/usr/local/lib$ ldd libueye_stream.so
    linux-vdso.so.1 (0x00007ffe467a0000)
    libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fb6c8879000)
    libliveMedia.so.52 => /usr/local/lib/ueye_olga/libliveMedia.so.52 (0x00007fb6c8565000)
    libgroupsock.so.8 => /usr/local/lib/ueye_olga/libgroupsock.so.8 (0x00007fb6c834b000)
    libBasicUsageEnvironment.so.1 => /usr/local/lib/ueye_olga/libBasicUsageEnvironment.so.1 (0x00007fb6c8141000)
    libUsageEnvironment.so.3 => /usr/local/lib/ueye_olga/libUsageEnvironment.so.3 (0x00007fb6c7f3e000)
    libavcodec.so.56 => /usr/local/lib/ueye_olga/libavcodec.so.56 (0x00007fb6c6ad1000)
    libavfilter.so.5 => /usr/local/lib/ueye_olga/libavfilter.so.5 (0x00007fb6c68b2000)
    libavutil.so.54 => /usr/local/lib/ueye_olga/libavutil.so.54 (0x00007fb6c664c000)
    libswscale.so.3 => /usr/local/lib/ueye_olga/libswscale.so.3 (0x00007fb6c63be000)
    libavformat.so.56 => /usr/local/lib/ueye_olga/libavformat.so.56 (0x00007fb6c60a5000)
    libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007fb6c5d1c000)
    libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007fb6c597e000)
    libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007fb6c5766000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fb6c5375000)
    /lib64/ld-linux-x86-64.so.2 (0x00007fb6c8cb2000)
    libswresample.so.1 => /usr/local/lib/ueye_olga/libswresample.so.1 (0x00007fb6c515b000)
    libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x00007fb6c4f3e000)
    librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007fb6c4d36000)

Нет, что libueye_stream.so с мягкими ссылками, перемещенными в /usr/local/lib.

make успешно : 

olga@olga-MS-7758:~/camera/ueye/ueye_stream/ueye_stream_x64/src/SimpleStreamer/build$ make
[ 50%] Linking CXX executable SimpleStream
[100%] Built target SimpleStream

11
задан Bill the Lizard 16 September 2012 в 22:24
поделиться

4 ответа

Рассмотрение набора S из N элементы и данное подмножество, каждый элемент или делают или не принадлежат тому подмножеству. Поэтому 2^N возможные подмножества (при включении исходных и пустых множеств), и существуют прямое отображение от битов в двоичном представлении x между 0 и 2^N к элементам в xподмножество th S.

После того как Вы разработали, как перечислить элементы данного подмножества, добавление, что значения просты.

Для нахождения подмножеств, которые равняются общему количеству t для большого N, одна оптимизация могла бы быть должна записать те подмножества, которые превышают t, и не тестируют любого, которые являются надлежащими надмножествами тех. Тестирование, ли определенный номер x надмножество набора y может быть достигнут с единственной битовой операцией и целочисленным сравнением.

12
ответ дан 3 December 2019 в 04:14
поделиться

Это был один из моих проектов колледжа 4/5 несколько лет назад, и я не могу напомнить алгоритму хорошо. Как я вижу и мои подачи памяти, это использует массив в качестве исходного набора и битовой маски для указания на то, какие элементы присутствуют в текущем подмножестве.
вот непротестированный код из архива:

#include <iostream>

#ifndef H_SUBSET
#define H_SUBSET

template <class T>
class Subset {
    private:
        int Dimension;
        T *Set;
        bool *Bitmask;
    public:
        Subset(T *set, int dim);
        ~Subset(void);
        void Show(void);
        void NextSubset(void);
        void EmptySet(void);
        void FullSet(void);
        int SubsetCardinality(void);
        int SetCardinality(void);
        T operator[](int index);
};      

template <class T>
int Subset<T>::SetCardinality(void) {
    return Dimension;
}

template <class T>
int Subset<T>::SubsetCardinality(void) {
    int dim = 0;
    for(int i = 0; i<Dimension; i++) {
        if(Bitmask[i]) {
            dim++;
        }
    }
    return dim;
}

template <class T>
void Subset<T>::EmptySet(void) {
    for(int i = 0; i<Dimension; i++) {
        Bitmask[i] = 0;
    }
    return;
}

template <class T>
void Subset<T>::FullSet(void) {
    for(int i = 0; i<Dimension; i++) {
        Bitmask[i] = 1;
    }
    return;
}

template <class T>
void Subset<T>::NextSubset(void) {
    int i = Dimension - 1;
    while(!Bitmask[i]&&i>=0) {
        i--;
        if(i<0) {
            break;
        }
    }
    if(i>=0) {
        Bitmask[i] = !Bitmask[i];
    }
    for(int j = i+1; j < Dimension; j++) {
        Bitmask[j] = !Bitmask[j];
    }
    return;
}

template <class T>
void Subset<T>::Show(void) {
    std::cout << "{ ";
    for(int i=0; i<Dimension; i++) {
        if(Bitmask[i]) {
            std::cout << Set[i] << ", ";
        }
    }
    std::cout << "}";
    return;
}

template <class T>
Subset<T>::Subset(T *set, int dim) {
    Set = new T[dim];
    Bitmask = new bool[dim];
    Dimension = dim;
    for(int i=0; i<dim; i++) {
        Set[i] = set[i];
        Bitmask[i] = true;
    }
}

template <class T>
Subset<T>::~Subset(void) {
    delete [] Set;
    delete [] Bitmask;
}
#endif // H_SUBSET

И если это - Ваша домашняя работа, Вы уничтожаете себя брат ;)

5
ответ дан 3 December 2019 в 04:14
поделиться

То, что Вы ищете, называют степенным множеством. Rosetta Code имеет много различных реализаций, но здесь является их кодом C++ (они используют вектор вместо массива, но должно быть довольно легко перевести).

#include <iostream>
#include <set>
#include <vector>
#include <iterator>

typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;

powerset_type powerset(set_type const& set)
{
  typedef set_type::const_iterator set_iter;
  typedef std::vector<set_iter> vec;
  typedef vec::iterator vec_iter;

  struct local
  {
    static int dereference(set_iter v) { return *v; }
  };

  powerset_type result;

  vec elements;
  do
  {
    set_type tmp;
    std::transform(elements.begin(), elements.end(),
                   std::inserter(tmp, tmp.end()),
                   local::dereference);
    result.insert(tmp);
    if (!elements.empty() && ++elements.back() == set.end())
    {
      elements.pop_back();
    }
    else
    {
      set_iter iter;
      if (elements.empty())
      {
        iter = set.begin();
      }
      else
      {
        iter = elements.back();
        ++iter;
      }
      for (; iter != set.end(); ++iter)
      {
        elements.push_back(iter);
      }
    }
  } while (!elements.empty());

  return result;
}

int main()
{
  int values[4] = { 2, 3, 5, 7 };
  set_type test_set(values, values+4);

  powerset_type test_powerset = powerset(test_set);

  for (powerset_type::iterator iter = test_powerset.begin();
       iter != test_powerset.end();
       ++iter)
  {
    std::cout << "{ ";
    char const* prefix = "";
    for (set_type::iterator iter2 = iter->begin();
         iter2 != iter->end();
         ++iter2)
    {
      std::cout << prefix << *iter2;
      prefix = ", ";
    }
    std::cout << " }\n";
  }
}

Вывод:

{  }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }
7
ответ дан 3 December 2019 в 04:14
поделиться

Сделайте Вас;

A) Действительно хотите найти все возможные подмножества?

или

B) Хотите найти, сколько элементов в массиве может быть объединено, чтобы равняться данному числу и видеть A) как шаг к решению?

Если это - A) затем, это довольно просто, но количество возможных подмножеств становится смехотворно большим очень быстро.

Если это - B) затем, необходимо отсортировать массив сначала и работать оттуда.

1
ответ дан 3 December 2019 в 04:14
поделиться
Другие вопросы по тегам:

Похожие вопросы: