make tuples, C++ (vc++)

make tuples

Language: Layout:

//Microsoft (R) C/C++ Optimizing Compiler Version 19.00.23506 for x64

#include <iostream>
#include <vector>
#include <cassert>

void add_tuples( const std::vector< std::vector<int> >& vectors, std::size_t pos,
                 std::vector<int> prefix, std::vector< std::vector<int> >& result )
{
    if( pos == vectors.size() ) result.push_back(prefix) ;
    else if( vectors[pos].empty() ) add_tuples( vectors, pos+1, prefix, result ) ; // note: skip empty vectors
    else
    {
        for( int v : vectors[pos] )
        {
            prefix.push_back(v) ;
            add_tuples( vectors, pos+1, prefix, result ) ;
            prefix.pop_back() ;
        }
    }
}

std::vector< std::vector<int> > make_tuples( const std::vector< std::vector<int> >& vectors )
{
    std::vector< std::vector<int> > result ;
    add_tuples( vectors, 0, {}, result ) ;
    return result ;
}

int main()
{
    const std::vector< std::vector<int> > vectors =  { {1,2,3}, {1,2,3}, {}, {1,2,3,4,5}, {}, {1,2}, {1,2,3} } ;

const auto tuples = make_tuples(vectors) ;

std::size_t ntups = 0 ;
    for( const auto& tup : tuples )
    {
        std::cout << ++ntups << ". [ " ;
        for( int v : tup ) std::cout << v << ' ' ;
        std::cout << "]\n" ;
    }

/////////////////////////////////////////////////////////////////////////////////
    ////////////////////////// sanity checks ////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////////////
    
    std::size_t num_empty_vecs = 0 ;
    std::size_t expected_ntups = 1 ;
    for( const auto& vec : vectors )
    {
        if( !vec.empty() ) expected_ntups *= vec.size() ;
        else ++num_empty_vecs ;
    }

assert( num_empty_vecs < vectors.size() && ntups == expected_ntups ) ;

std::cout << "\n------------\n\n"
              << "#vectors: " << vectors.size() << '\n'
              << "  #empty: " << num_empty_vecs << '\n'
              << "tup size: " << vectors.size() - num_empty_vecs << '\n'
              << " #tuples: " << ntups << '\n' ;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 2,06 sec, absolute running time: 0,22 sec, absolute service time: 2,3 sec

1. [ 1 1 1 1 1 ] 2. [ 1 1 1 1 2 ] 3. [ 1 1 1 1 3 ] 4. [ 1 1 1 2 1 ] 5. [ 1 1 1 2 2 ] 6. [ 1 1 1 2 3 ] 7. [ 1 1 2 1 1 ] 8. [ 1 1 2 1 2 ] 9. [ 1 1 2 1 3 ] 10. [ 1 1 2 2 1 ] 11. [ 1 1 2 2 2 ] 12. [ 1 1 2 2 3 ] 13. [ 1 1 3 1 1 ] 14. [ 1 1 3 1 2 ] 15. [ 1 1 3 1 3 ] 16. [ 1 1 3 2 1 ] 17. [ 1 1 3 2 2 ] 18. [ 1 1 3 2 3 ] 19. [ 1 1 4 1 1 ] 20. [ 1 1 4 1 2 ] 21. [ 1 1 4 1 3 ] 22. [ 1 1 4 2 1 ] 23. [ 1 1 4 2 2 ] 24. [ 1 1 4 2 3 ] 25. [ 1 1 5 1 1 ] 26. [ 1 1 5 1 2 ] 27. [ 1 1 5 1 3 ] 28. [ 1 1 5 2 1 ] 29. [ 1 1 5 2 2 ] 30. [ 1 1 5 2 3 ] 31. [ 1 2 1 1 1 ] 32. [ 1 2 1 1 2 ] 33. [ 1 2 1 1 3 ] 34. [ 1 2 1 2 1 ] 35. [ 1 2 1 2 2 ] 36. [ 1 2 1 2 3 ] 37. [ 1 2 2 1 1 ] 38. [ 1 2 2 1 2 ] 39. [ 1 2 2 1 3 ] 40. [ 1 2 2 2 1 ] 41. [ 1 2 2 2 2 ] 42. [ 1 2 2 2 3 ] 43. [ 1 2 3 1 1 ] 44. [ 1 2 3 1 2 ] 45. [ 1 2 3 1 3 ] 46. [ 1 2 3 2 1 ] 47. [ 1 2 3 2 2 ] 48. [ 1 2 3 2 3 ] 49. [ 1 2 4 1 1 ] 50. [ 1 2 4 1 2 ] 51. [ 1 2 4 1 3 ] 52. [ 1 2 4 2 1 ] 53. [ 1 2 4 2 2 ] 54. [ 1 2 4 2 3 ] 55. [ 1 2 5 1 1 ] 56. [ 1 2 5 1 2 ] 57. [ 1 2 5 1 3 ] 58. [ 1 2 5 2 1 ] 59. [ 1 2 5 2 2 ] 60. [ 1 2 5 2 3 ] 61. [ 1 3 1 1 1 ] 62. [ 1 3 1 1 2 ] 63. [ 1 3 1 1 3 ] 64. [ 1 3 1 2 1 ] 65. [ 1 3 1 2 2 ] 66. [ 1 3 1 2 3 ] 67. [ 1 3 2 1 1 ] 68. [ 1 3 2 1 2 ] 69. [ 1 3 2 1 3 ] 70. [ 1 3 2 2 1 ] 71. [ 1 3 2 2 2 ] 72. [ 1 3 2 2 3 ] 73. [ 1 3 3 1 1 ] 74. [ 1 3 3 1 2 ] 75. [ 1 3 3 1 3 ] 76. [ 1 3 3 2 1 ] 77. [ 1 3 3 2 2 ] 78. [ 1 3 3 2 3 ] 79. [ 1 3 4 1 1 ] 80. [ 1 3 4 1 2 ] 81. [ 1 3 4 1 3 ] 82. [ 1 3 4 2 1 ] 83. [ 1 3 4 2 2 ] 84. [ 1 3 4 2 3 ] 85. [ 1 3 5 1 1 ] 86. [ 1 3 5 1 2 ] 87. [ 1 3 5 1 3 ] 88. [ 1 3 5 2 1 ] 89. [ 1 3 5 2 2 ] 90. [ 1 3 5 2 3 ] 91. [ 2 1 1 1 1 ] 92. [ 2 1 1 1 2 ] 93. [ 2 1 1 1 3 ] 94. [ 2 1 1 2 1 ] 95. [ 2 1 1 2 2 ] 96. [ 2 1 1 2 3 ] 97. [ 2 1 2 1 1 ] 98. [ 2 1 2 1 2 ] 99. [ 2 1 2 1 3 ] 100. [ 2 1 2 2 1 ] 101. [ 2 1 2 2 2 ] 102. [ 2 1 2 2 3 ] 103. [ 2 1 3 1 1 ] 104. [ 2 1 3 1 2 ] 105. [ 2 1 3 1 3 ] 106. [ 2 1 3 2 1 ] 107. [ 2 1 3 2 2 ] 108. [ 2 1 3 2 3 ] 109. [ 2 1 4 1 1 ] 110. [ 2 1 4 1 2 ] 111. [ 2 1 4 1 3 ] 112. [ 2 1 4 2 1 ] 113. [ 2 1 4 2 2 ] 114. [ 2 1 4 2 3 ] 115. [ 2 1 5 1 1 ] 116. [ 2 1 5 1 2 ] 117. [ 2 1 5 1 3 ] 118. [ 2 1 5 2 1 ] 119. [ 2 1 5 2 2 ] 120. [ 2 1 5 2 3 ] 121. [ 2 2 1 1 1 ] 122. [ 2 2 1 1 2 ] 123. [ 2 2 1 1 3 ] 124. [ 2 2 1 2 1 ] 125. [ 2 2 1 2 2 ] 126. [ 2 2 1 2 3 ] 127. [ 2 2 2 1 1 ] 128. [ 2 2 2 1 2 ] 129. [ 2 2 2 1 3 ] 130. [ 2 2 2 2 1 ] 131. [ 2 2 2 2 2 ] 132. [ 2 2 2 2 3 ] 133. [ 2 2 3 1 1 ] 134. [ 2 2 3 1 2 ] 135. [ 2 2 3 1 3 ] 136. [ 2 2 3 2 1 ] 137. [ 2 2 3 2 2 ] 138. [ 2 2 3 2 3 ] 139. [ 2 2 4 1 1 ] 140. [ 2 2 4 1 2 ] 141. [ 2 2 4 1 3 ] 142. [ 2 2 4 2 1 ] 143. [ 2 2 4 2 2 ] 144. [ 2 2 4 2 3 ] 145. [ 2 2 5 1 1 ] 146. [ 2 2 5 1 2 ] 147. [ 2 2 5 1 3 ] 148. [ 2 2 5 2 1 ] 149. [ 2 2 5 2 2 ] 150. [ 2 2 5 2 3 ] 151. [ 2 3 1 1 1 ] 152. [ 2 3 1 1 2 ] 153. [ 2 3 1 1 3 ] 154. [ 2 3 1 2 1 ] 155. [ 2 3 1 2 2 ] 156. [ 2 3 1 2 3 ] 157. [ 2 3 2 1 1 ] 158. [ 2 3 2 1 2 ] 159. [ 2 3 2 1 3 ] 160. [ 2 3 2 2 1 ] 161. [ 2 3 2 2 2 ] 162. [ 2 3 2 2 3 ] 163. [ 2 3 3 1 1 ] 164. [ 2 3 3 1 2 ] 165. [ 2 3 3 1 3 ] 166. [ 2 3 3 2 1 ] 167. [ 2 3 3 2 2 ] 168. [ 2 3 3 2 3 ] 169. [ 2 3 4 1 1 ] 170. [ 2 3 4 1 2 ] 171. [ 2 3 4 1 3 ] 172. [ 2 3 4 2 1 ] 173. [ 2 3 4 2 2 ] 174. [ 2 3 4 2 3 ] 175. [ 2 3 5 1 1 ] 176. [ 2 3 5 1 2 ] 177. [ 2 3 5 1 3 ] 178. [ 2 3 5 2 1 ] 179. [ 2 3 5 2 2 ] 180. [ 2 3 5 2 3 ] 181. [ 3 1 1 1 1 ] 182. [ 3 1 1 1 2 ] 183. [ 3 1 1 1 3 ] 184. [ 3 1 1 2 1 ] 185. [ 3 1 1 2 2 ] 186. [ 3 1 1 2 3 ] 187. [ 3 1 2 1 1 ] 188. [ 3 1 2 1 2 ] 189. [ 3 1 2 1 3 ] 190. [ 3 1 2 2 1 ] 191. [ 3 1 2 2 2 ] 192. [ 3 1 2 2 3 ] 193. [ 3 1 3 1 1 ] 194. [ 3 1 3 1 2 ] 195. [ 3 1 3 1 3 ] 196. [ 3 1 3 2 1 ] 197. [ 3 1 3 2 2 ] 198. [ 3 1 3 2 3 ] 199. [ 3 1 4 1 1 ] 200. [ 3 1 4 1 2 ] 201. [ 3 1 4 1 3 ] 202. [ 3 1 4 2 1 ] 203. [ 3 1 4 2 2 ] 204. [ 3 1 4 2 3 ] 205. [ 3 1 5 1 1 ] 206. [ 3 1 5 1 2 ] 207. [ 3 1 5 1 3 ] 208. [ 3 1 5 2 1 ] 209. [ 3 1 5 2 2 ] 210. [ 3 1 5 2 3 ] 211. [ 3 2 1 1 1 ] 212. [ 3 2 1 1 2 ] 213. [ 3 2 1 1 3 ] 214. [ 3 2 1 2 1 ] 215. [ 3 2 1 2 2 ] 216. [ 3 2 1 2 3 ] 217. [ 3 2 2 1 1 ] 218. [ 3 2 2 1 2 ] 219. [ 3 2 2 1 3 ] 220. [ 3 2 2 2 1 ] 221. [ 3 2 2 2 2 ] 222. [ 3 2 2 2 3 ] 223. [ 3 2 3 1 1 ] 224. [ 3 2 3 1 2 ] 225. [ 3 2 3 1 3 ] 226. [ 3 2 3 2 1 ] 227. [ 3 2 3 2 2 ] 228. [ 3 2 3 2 3 ] 229. [ 3 2 4 1 1 ] 230. [ 3 2 4 1 2 ] 231. [ 3 2 4 1 3 ] 232. [ 3 2 4 2 1 ] 233. [ 3 2 4 2 2 ] 234. [ 3 2 4 2 3 ] 235. [ 3 2 5 1 1 ] 236. [ 3 2 5 1 2 ] 237. [ 3 2 5 1 3 ] 238. [ 3 2 5 2 1 ] 239. [ 3 2 5 2 2 ] 240. [ 3 2 5 2 3 ] 241. [ 3 3 1 1 1 ] 242. [ 3 3 1 1 2 ] 243. [ 3 3 1 1 3 ] 244. [ 3 3 1 2 1 ] 245. [ 3 3 1 2 2 ] 246. [ 3 3 1 2 3 ] 247. [ 3 3 2 1 1 ] 248. [ 3 3 2 1 2 ] 249. [ 3 3 2 1 3 ] 250. [ 3 3 2 2 1 ] 251. [ 3 3 2 2 2 ] 252. [ 3 3 2 2 3 ] 253. [ 3 3 3 1 1 ] 254. [ 3 3 3 1 2 ] 255. [ 3 3 3 1 3 ] 256. [ 3 3 3 2 1 ] 257. [ 3 3 3 2 2 ] 258. [ 3 3 3 2 3 ] 259. [ 3 3 4 1 1 ] 260. [ 3 3 4 1 2 ] 261. [ 3 3 4 1 3 ] 262. [ 3 3 4 2 1 ] 263. [ 3 3 4 2 2 ] 264. [ 3 3 4 2 3 ] 265. [ 3 3 5 1 1 ] 266. [ 3 3 5 1 2 ] 267. [ 3 3 5 1 3 ] 268. [ 3 3 5 2 1 ] 269. [ 3 3 5 2 2 ] 270. [ 3 3 5 2 3 ] ------------ #vectors: 7 #empty: 2 tup size: 5 #tuples: 270