fork download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3. #include <vector>
  4.  
  5. // Permutations N threads.
  6. int64_t f(std::vector<int64_t> nodes)
  7. {
  8.   size_t N = nodes.size();
  9.  
  10.   // In the case of 0 threads there is 1 permutation.
  11.   if (N == 0)
  12.     return 1;
  13.  
  14.   // Each of the existing threads should have at least one node.
  15.   bool have_all_one_node = true;
  16.   std::vector<int64_t> v;
  17.   for (auto s : nodes)
  18.   {
  19.     if (s == 0)
  20.       have_all_one_node = false;
  21.     else
  22.       v.push_back(s);
  23.   }
  24.   if (!have_all_one_node)
  25.     return f(v);
  26.  
  27.   // In the case of 1 thread, each node can only be connected
  28.   // to itself; so one permutation.
  29.   if (N == 1)
  30.     return 1;
  31.  
  32.   // Otherwise we run over all possible ways the first
  33.   // node of the first thread can be connected and sum
  34.   // the results.
  35.  
  36.   // Firstly, this node can be self-connected.
  37.   --v[0];
  38.   int64_t sum = f(v);
  39.  
  40.   // Otherwise it is connected one of the remaining threads.
  41.   for (size_t i = 1; i < N; ++i)
  42.   {
  43.     --v[i];
  44.     sum += (v[i] + 1) * f(v);
  45.     ++v[i];
  46.   }
  47.  
  48.   return sum;
  49. }
  50.  
  51. int main()
  52. {
  53.   int number_of_threads;
  54.   int nodes_per_thread;
  55.  
  56.   std::cin >> number_of_threads >> nodes_per_thread;
  57.  
  58.   std::vector<int64_t> v(number_of_threads, nodes_per_thread);
  59.   std::cout << "#threads: " << number_of_threads << ", #nodes/thread: " << nodes_per_thread << ", permutations: " << f(v) << std::endl;
  60. }
  61.  
  62.  
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
4
3
stdout
copy 
#threads: 4, #nodes/thread: 3, permutations: 60058
https://ideone.com/XjF1Ci
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!