{"action":"created","comment":{"url":"https://api.github.com/repos/racket/racket/pulls/comments/49035189","id":49035189,"diff_hunk":"@@ -588,6 +590,96 @@\n     (vector-set! a j x))\n   (vector->list a))\n \n+(define (combinations l [k #f])\n+  (for/list ([x (in-combinations l k)]) x))\n+\n+;; Generate combinations of the list `l`.\n+;; - If `k` is a natural number, generate all combinations of size `k`.\n+;; - If `k` is #f, generate all combinations of any size (powerset of `l`).\n+(define (in-combinations l [k #f])\n+  (unless (list? l)\n+    (raise-argument-error 'in-combinations \"list?\" 0 l))\n+  (when (and k (not (exact-nonnegative-integer? k)))\n+    (raise-argument-error 'in-combinations \"(or #f exact-nonnegative-integer?)\" 1 k))\n+  (let* ([v       (list->vector l)]\n+         [N       (vector-length v)]\n+         [N-1     (- N 1)])\n+    (letrec ([gen-combinations\n+              (cond\n+                [(not k)\n+                 ;; Enumerate all binary numbers [1..2**N].\n+                 ;; Produce the combination with elements in `v` at the same\n+                 ;;  positions as the 1's in the binary number.\n+                 (let* ([num-incrs (- (expt 2 N) 1)]\n+                        [b*        (make-vector N #f)] ;; Binary counter\n+                        [b*-incr","path":"racket/collects/racket/list.rkt","position":35,"original_position":35,"commit_id":"637c05bdc7b69faf8a19859f9e4b42073484b03d","original_commit_id":"637c05bdc7b69faf8a19859f9e4b42073484b03d","user":{"login":"stamourv","id":854429,"avatar_url":"https://avatars.githubusercontent.com/u/854429?v=3","gravatar_id":"","url":"https://api.github.com/users/stamourv","html_url":"https://github.com/stamourv","followers_url":"https://api.github.com/users/stamourv/followers","following_url":"https://api.github.com/users/stamourv/following{/other_user}","gists_url":"https://api.github.com/users/stamourv/gists{/gist_id}","starred_url":"https://api.github.com/users/stamourv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stamourv/subscriptions","organizations_url":"https://api.github.com/users/stamourv/orgs","repos_url":"https://api.github.com/users/stamourv/repos","events_url":"https://api.github.com/users/stamourv/events{/privacy}","received_events_url":"https://api.github.com/users/stamourv/received_events","type":"User","site_admin":false},"body":"Wouldn't the code be simpler if you used integers and bitwise ops?","created_at":"2016-01-07T02:06:07Z","updated_at":"2016-01-07T02:06:07Z","html_url":"https://github.com/racket/racket/pull/1175#discussion_r49035189","pull_request_url":"https://api.github.com/repos/racket/racket/pulls/1175","_links":{"self":{"href":"https://api.github.com/repos/racket/racket/pulls/comments/49035189"},"html":{"href":"https://github.com/racket/racket/pull/1175#discussion_r49035189"},"pull_request":{"href":"https://api.github.com/repos/racket/racket/pulls/1175"}}},"pull_request":{"url":"https://api.github.com/repos/racket/racket/pulls/1175","id":54274567,"html_url":"https://github.com/racket/racket/pull/1175","diff_url":"https://github.com/racket/racket/pull/1175.diff","patch_url":"https://github.com/racket/racket/pull/1175.patch","issue_url":"https://api.github.com/repos/racket/racket/issues/1175","number":1175,"state":"open","locked":false,"title":"Add 'combinations' and 'in-combinations'","user":{"login":"bennn","id":1731829,"avatar_url":"https://avatars.githubusercontent.com/u/1731829?v=3","gravatar_id":"","url":"https://api.github.com/users/bennn","html_url":"https://github.com/bennn","followers_url":"https://api.github.com/users/bennn/followers","following_url":"https://api.github.com/users/bennn/following{/other_user}","gists_url":"https://api.github.com/users/bennn/gists{/gist_id}","starred_url":"https://api.github.com/users/bennn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bennn/subscriptions","organizations_url":"https://api.github.com/users/bennn/orgs","repos_url":"https://api.github.com/users/bennn/repos","events_url":"https://api.github.com/users/bennn/events{/privacy}","received_events_url":"https://api.github.com/users/bennn/received_events","type":"User","site_admin":false},"body":"New functions for `racket/list`, to accompany `*permutations`.\r\n\r\nBesides converting the input list to a vector, `in-combinations` runs in constant space. For time:\r\n\r\n```\r\n(define x* (range 25))\r\n\r\n(let ([c* (time (in-combinations x*))])\r\n  (time (for ([x c*]) (void))))\r\n;; cpu time: 1 real time: 1 gc time: 0\r\n;; cpu time: 14581 real time: 15424 gc time: 777\r\n\r\n(let ([c* (time (in-combinations x* 5))])\r\n      (time (for ([x c*]) (void))))\r\n;; cpu time: 0 real time: 0 gc time: 0\r\n;; cpu time: 2 real time: 2 gc time: 0\r\n```\r\n\r\nIf you'd rather the implementation was split across 2 functions `(in-combinations n k)` and `(in-powerset n)` I'll happily do that, but I think the name `combinations` is more intuitive. (If there's any way to redirect searches for \"powerset\" to return \"combinations\", we should add that.)","created_at":"2015-12-21T16:22:35Z","updated_at":"2016-01-07T02:06:07Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b37a512b03f7ca3e5236a4b8ec31696b169df3cf","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/racket/racket/pulls/1175/commits","review_comments_url":"https://api.github.com/repos/racket/racket/pulls/1175/comments","review_comment_url":"https://api.github.com/repos/racket/racket/pulls/comments{/number}","comments_url":"https://api.github.com/repos/racket/racket/issues/1175/comments","statuses_url":"https://api.github.com/repos/racket/racket/statuses/637c05bdc7b69faf8a19859f9e4b42073484b03d","head":{"label":"bennn:combinations","ref":"combinations","sha":"637c05bdc7b69faf8a19859f9e4b42073484b03d","user":{"login":"bennn","id":1731829,"avatar_url":"https://avatars.githubusercontent.com/u/1731829?v=3","gravatar_id":"","url":"https://api.github.com/users/bennn","html_url":"https://github.com/bennn","followers_url":"https://api.github.com/users/bennn/followers","following_url":"https://api.github.com/users/bennn/following{/other_user}","gists_url":"https://api.github.com/users/bennn/gists{/gist_id}","starred_url":"https://api.github.com/users/bennn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bennn/subscriptions","organizations_url":"https://api.github.com/users/bennn/orgs","repos_url":"https://api.github.com/users/bennn/repos","events_url":"https://api.github.com/users/bennn/events{/privacy}","received_events_url":"https://api.github.com/users/bennn/received_events","type":"User","site_admin":false},"repo":{"id":18584623,"name":"racket","full_name":"bennn/racket","owner":{"login":"bennn","id":1731829,"avatar_url":"https://avatars.githubusercontent.com/u/1731829?v=3","gravatar_id":"","url":"https://api.github.com/users/bennn","html_url":"https://github.com/bennn","followers_url":"https://api.github.com/users/bennn/followers","following_url":"https://api.github.com/users/bennn/following{/other_user}","gists_url":"https://api.github.com/users/bennn/gists{/gist_id}","starred_url":"https://api.github.com/users/bennn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bennn/subscriptions","organizations_url":"https://api.github.com/users/bennn/orgs","repos_url":"https://api.github.com/users/bennn/repos","events_url":"https://api.github.com/users/bennn/events{/privacy}","received_events_url":"https://api.github.com/users/bennn/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/bennn/racket","description":"The Racket repository","fork":true,"url":"https://api.github.com/repos/bennn/racket","forks_url":"https://api.github.com/repos/bennn/racket/forks","keys_url":"https://api.github.com/repos/bennn/racket/keys{/key_id}","collaborators_url":"https://api.github.com/repos/bennn/racket/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/bennn/racket/teams","hooks_url":"https://api.github.com/repos/bennn/racket/hooks","issue_events_url":"https://api.github.com/repos/bennn/racket/issues/events{/number}","events_url":"https://api.github.com/repos/bennn/racket/events","assignees_url":"https://api.github.com/repos/bennn/racket/assignees{/user}","branches_url":"https://api.github.com/repos/bennn/racket/branches{/branch}","tags_url":"https://api.github.com/repos/bennn/racket/tags","blobs_url":"https://api.github.com/repos/bennn/racket/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/bennn/racket/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/bennn/racket/git/refs{/sha}","trees_url":"https://api.github.com/repos/bennn/racket/git/trees{/sha}","statuses_url":"https://api.github.com/repos/bennn/racket/statuses/{sha}","languages_url":"https://api.github.com/repos/bennn/racket/languages","stargazers_url":"https://api.github.com/repos/bennn/racket/stargazers","contributors_url":"https://api.github.com/repos/bennn/racket/contributors","subscribers_url":"https://api.github.com/repos/bennn/racket/subscribers","subscription_url":"https://api.github.com/repos/bennn/racket/subscription","commits_url":"https://api.github.com/repos/bennn/racket/commits{/sha}","git_commits_url":"https://api.github.com/repos/bennn/racket/git/commits{/sha}","comments_url":"https://api.github.com/repos/bennn/racket/comments{/number}","issue_comment_url":"https://api.github.com/repos/bennn/racket/issues/comments{/number}","contents_url":"https://api.github.com/repos/bennn/racket/contents/{+path}","compare_url":"https://api.github.com/repos/bennn/racket/compare/{base}...{head}","merges_url":"https://api.github.com/repos/bennn/racket/merges","archive_url":"https://api.github.com/repos/bennn/racket/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/bennn/racket/downloads","issues_url":"https://api.github.com/repos/bennn/racket/issues{/number}","pulls_url":"https://api.github.com/repos/bennn/racket/pulls{/number}","milestones_url":"https://api.github.com/repos/bennn/racket/milestones{/number}","notifications_url":"https://api.github.com/repos/bennn/racket/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/bennn/racket/labels{/name}","releases_url":"https://api.github.com/repos/bennn/racket/releases{/id}","created_at":"2014-04-09T04:00:26Z","updated_at":"2015-02-12T22:32:25Z","pushed_at":"2016-01-06T20:42:58Z","git_url":"git://github.com/bennn/racket.git","ssh_url":"git@github.com:bennn/racket.git","clone_url":"https://github.com/bennn/racket.git","svn_url":"https://github.com/bennn/racket","homepage":"http://racket-lang.org/","size":162679,"stargazers_count":0,"watchers_count":0,"language":"Racket","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"racket:master","ref":"master","sha":"3a4ba9a1ca31a83dcb9704ac8e464e15f505e579","user":{"login":"racket","id":232371,"avatar_url":"https://avatars.githubusercontent.com/u/232371?v=3","gravatar_id":"","url":"https://api.github.com/users/racket","html_url":"https://github.com/racket","followers_url":"https://api.github.com/users/racket/followers","following_url":"https://api.github.com/users/racket/following{/other_user}","gists_url":"https://api.github.com/users/racket/gists{/gist_id}","starred_url":"https://api.github.com/users/racket/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/racket/subscriptions","organizations_url":"https://api.github.com/users/racket/orgs","repos_url":"https://api.github.com/users/racket/repos","events_url":"https://api.github.com/users/racket/events{/privacy}","received_events_url":"https://api.github.com/users/racket/received_events","type":"Organization","site_admin":false},"repo":{"id":615969,"name":"racket","full_name":"racket/racket","owner":{"login":"racket","id":232371,"avatar_url":"https://avatars.githubusercontent.com/u/232371?v=3","gravatar_id":"","url":"https://api.github.com/users/racket","html_url":"https://github.com/racket","followers_url":"https://api.github.com/users/racket/followers","following_url":"https://api.github.com/users/racket/following{/other_user}","gists_url":"https://api.github.com/users/racket/gists{/gist_id}","starred_url":"https://api.github.com/users/racket/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/racket/subscriptions","organizations_url":"https://api.github.com/users/racket/orgs","repos_url":"https://api.github.com/users/racket/repos","events_url":"https://api.github.com/users/racket/events{/privacy}","received_events_url":"https://api.github.com/users/racket/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/racket/racket","description":"The Racket repository","fork":false,"url":"https://api.github.com/repos/racket/racket","forks_url":"https://api.github.com/repos/racket/racket/forks","keys_url":"https://api.github.com/repos/racket/racket/keys{/key_id}","collaborators_url":"https://api.github.com/repos/racket/racket/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/racket/racket/teams","hooks_url":"https://api.github.com/repos/racket/racket/hooks","issue_events_url":"https://api.github.com/repos/racket/racket/issues/events{/number}","events_url":"https://api.github.com/repos/racket/racket/events","assignees_url":"https://api.github.com/repos/racket/racket/assignees{/user}","branches_url":"https://api.github.com/repos/racket/racket/branches{/branch}","tags_url":"https://api.github.com/repos/racket/racket/tags","blobs_url":"https://api.github.com/repos/racket/racket/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/racket/racket/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/racket/racket/git/refs{/sha}","trees_url":"https://api.github.com/repos/racket/racket/git/trees{/sha}","statuses_url":"https://api.github.com/repos/racket/racket/statuses/{sha}","languages_url":"https://api.github.com/repos/racket/racket/languages","stargazers_url":"https://api.github.com/repos/racket/racket/stargazers","contributors_url":"https://api.github.com/repos/racket/racket/contributors","subscribers_url":"https://api.github.com/repos/racket/racket/subscribers","subscription_url":"https://api.github.com/repos/racket/racket/subscription","commits_url":"https://api.github.com/repos/racket/racket/commits{/sha}","git_commits_url":"https://api.github.com/repos/racket/racket/git/commits{/sha}","comments_url":"https://api.github.com/repos/racket/racket/comments{/number}","issue_comment_url":"https://api.github.com/repos/racket/racket/issues/comments{/number}","contents_url":"https://api.github.com/repos/racket/racket/contents/{+path}","compare_url":"https://api.github.com/repos/racket/racket/compare/{base}...{head}","merges_url":"https://api.github.com/repos/racket/racket/merges","archive_url":"https://api.github.com/repos/racket/racket/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/racket/racket/downloads","issues_url":"https://api.github.com/repos/racket/racket/issues{/number}","pulls_url":"https://api.github.com/repos/racket/racket/pulls{/number}","milestones_url":"https://api.github.com/repos/racket/racket/milestones{/number}","notifications_url":"https://api.github.com/repos/racket/racket/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/racket/racket/labels{/name}","releases_url":"https://api.github.com/repos/racket/racket/releases{/id}","created_at":"2010-04-18T06:39:16Z","updated_at":"2016-01-06T23:14:24Z","pushed_at":"2016-01-07T01:52:39Z","git_url":"git://github.com/racket/racket.git","ssh_url":"git@github.com:racket/racket.git","clone_url":"https://github.com/racket/racket.git","svn_url":"https://github.com/racket/racket","homepage":"http://racket-lang.org/","size":187207,"stargazers_count":1300,"watchers_count":1300,"language":"Racket","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":272,"mirror_url":null,"open_issues_count":108,"forks":272,"open_issues":108,"watchers":1300,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/racket/racket/pulls/1175"},"html":{"href":"https://github.com/racket/racket/pull/1175"},"issue":{"href":"https://api.github.com/repos/racket/racket/issues/1175"},"comments":{"href":"https://api.github.com/repos/racket/racket/issues/1175/comments"},"review_comments":{"href":"https://api.github.com/repos/racket/racket/pulls/1175/comments"},"review_comment":{"href":"https://api.github.com/repos/racket/racket/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/racket/racket/pulls/1175/commits"},"statuses":{"href":"https://api.github.com/repos/racket/racket/statuses/637c05bdc7b69faf8a19859f9e4b42073484b03d"}}}}