Draft
De Bruijn Sequences - Generation (Part 2)
Loading description...
Combinatorics
Performance
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Haskell translation
Please note I have updated the description: use double quotes for strings because Haskell reserves single quotes for single characters, moved the section explaining de Bruijn sequences up top, and minor updates to spelling, grammar and markup. If you disagree with any change, it can be changed again.
Looks great to me.
Shouldn't
n^kbek^n?Yes, thanks for catching that! I have changed it now.
Needs
performancetag and an indication of the required performance.n>1is a bit unlimited.This comment has been hidden.
( Please note CW does not generate notifications for spoilered replies. You can reply unspoileredly as well to draw attention to a spoilered one. )
I have not actually tried all naive approaches, but I tried at least two that timed out.
I think my solution is
O(n ^ k+1). You have to return a list of lengthn^k, so better than that should be plain impossible, and you'll always have some additional overhead.If you really want to do performance checking well, you'll need solutions of specific complexities that you want to time out to test your tests with.
Reasoning about time complexities is not easy here. You could just leave it at "such and such
k, such and suchn". Solvers know they have to generaten^k, so the worst case is known, and will preclude naive solutions.Thanks for the explanation and tips. RE: your last point, so would this be appropriate:
As we know at worst, they will generate every single de Bruijn sequence and then sort them?
I'll do some more testing anyway and see what I can workout.
Ω(k^n)andO(k!^(k^(n-1))/(k^n))I don't think anyone will figure out that last big-O. I have seen worse, but it's quite ridiculous. :P
I actually think "
O(n), wherenis length of output" would be the most understandable way of saying you have to be quite fast. And with tests ( or a test, at least ) of size8^7, about2million, I can't imagine anything slower than that will work.That is true, that upper bound is probably too broad đ I have amended the description as suggested and added the performance tag, many thanks.