Recursive functions

Something about writing a function that does the work by calling itself feels almost divine. Currently writing a unique permutation function. Pretty much functions correctly, first try, but not quite. Currently working out those issues.

Got it working. Was some dumb logic error where I was reading a bitfield backwards.

Some of the date stuff is wrong atm.

>>44573 >Something about writing a function that does the work by calling itself feels almost divine. Because it is divine. We exist on the surface of a fractal. It's the trick of life, we all get our own little bubble of the infinite ferment. Look at them, clutching it between their teeth, grinning as they go. Like they've gotten away with something...

>>44576 >Because it is divine. I never understood the fascination with recursion, or even why it is something that needs to be "learned" in the first place. It seems intuitive to me. Then again, I'm probably retarded.

>>44631 I didn't say it had to be learned, in fact it seems to be the opposite. The people who can do recursion already get it, and the people who encounter the concept and don't hit a hard cognitive ceiling. Kind of like how NPCs think logic and language are two sides of the same coin and can't do otherwise. The inability of some people to understand it, like the inability to simulate sensory input (eg imagining an apple) or the inability to choose whether they'll generate and listen to an "inner monologue", is what makes recursion interesting. It should be a priority to determine whether this is genetic and or due to some natural condition, or if it's a form of brain damage.

>>44632 yes glitterboy, you're very smart

>>44633 You're just feeling threatened / jealous. Meanwhile I don't think about you at all. In fact it isn't even possible because I barely have a "me" to begin with. There's nothing to compare to. I do experience burden and unrest in the form of dealing with your alien psychology.

If anyone wants to critique the code. It's C++. Takes an array of uint8_t (a number as decimal digits) and outputs all permutations. void digit_perm_work(uint8_t *digits, unsigned length, unsigned depth, std::vector<size_t> *permutations) { uint16_t unique = 0; for (unsigned i = 0; i < length; ++i) {unique |= (1 << digits[i]);} for (uint8_t i = 0; i <= 10 ; ++i) { if ((1 << i) & unique) { if (length == 1) { size_t multiplier = 1, result = 0; for (uint8_t *most_sig = digits - depth; digits >= most_sig; --digits, multiplier *= 10) { result += *digits * multiplier;} permutations->push_back(result); return; } for (unsigned n = 0; n < length; ++n) { if (digits[n] == i) {std::swap(digits[0], digits[n]); break;} } digit_perm_work(digits + 1, length - 1, depth + 1, permutations); } } return; } std::vector<size_t> digit_permutations (digit_set &set) { std::vector<size_t> ret; ret.reserve(32); uint8_t digit_copy[set.capacity()]; std::memcpy(digit_copy, set.data(), set.size()); digit_perm_work(digit_copy, set.size(), 0, &ret); return ret; } When you write it all out by hand the branching structure actually forms shapes, which are a sort of signature. I wanted to use intermediate tiers of the branches for something but haven't gotten around to it.

>>44636 Looks like it didn't preserve indentation...

>>44636 https://en.cppreference.com/cpp/algorithm/next_permutation

>>44638 Wasn't aware of this, thanks. I prefer to roll my own obviously. Eventually I'll probably profile performance differences. Mine could be optimized by subsequent calls re-using the unique bitfield, which may not be an improvement having to count occurrences. I also assume the STL implementation doesn't do unique permutations, so you'd have to run something over the output to remove duplicates.

>>44640 Actually it does do unique. It's more efficient this way however, the permutations are all converted back to binary. I'd like to get rid of either the length or depth variable.

>>44641 >Actually it does do unique Provided the input is already sorted... meh. This implementation takes arbitrary input and outputs it sorted in the process. High data locality. Compiler probably does something with the recursive variable reuse.

>>44640 >>44641 >>44642 The best thing about their approach is that they don't construct a whole ass vector of results. They just do something with permutation, then discard it and move to the next one, without collecting them all into a list. But still it's flexible and if you really want to collect them all, you can do that as well and clone/push current permutation to separate results list you manage yourself.

>>44643 It's being passed an array of bytes potentially holding a 64 bit number of decimal digits. I mean yeah, I could just print and sum them outside the loop in realtime, maintain a counter, etc. But why keep making and comparing all these pointers when I could reuse all of the steps it's already doing... I didn't want to put printing in the loop itself. I suppose I could though. Just pass a pointer to the sum variable in. hm. I guess don't ask for feedback on programming in general, especially to people who don't like you to begin with.

>>44644 > I guess don't ask for feedback on programming in general, especially to people who don't like you to begin with. Kek, take it easy, it's mostly a generic suggestion on potential usefulness of iterators. I didn't look closely into what you're doing there and I rarely work with numbers, but do iterator acrobatics every day for mundane things. That's why I feel compelled to suggest iterators, especially when it's C++ where they're omnipresent.

>>44632 >I didn't say it had to be learned I didn't say you did

>>44645 I was a bit overloaded earlier. Thanks for the feedback. >>44647 True.

>>44636 Passing a pointer to std::vector, im so sorry, who hurt you

>>44672 What do you mean? It's a recursive function, move semantics don't apply and passing by reference is basically the same.

>>44673 >>44636 Your uint8_t digit_copy isn't standards compliant, should replace with std::array or another std::vector

>>44674 Thought about it. I don't need the length variable of std::array (I guess it's contexpr anyway?) and the pointer to the "beginning" and length both have to change. So I used a plain array.