Distinct permutations of incomparable items#834
Merged
bbayles merged 25 commits intomore-itertools:masterfrom Jun 17, 2024
Merged
Distinct permutations of incomparable items#834bbayles merged 25 commits intomore-itertools:masterfrom
bbayles merged 25 commits intomore-itertools:masterfrom
Conversation
pochmann3
reviewed
May 2, 2024
more_itertools/more.py
Outdated
| items = sorted(iterable) | ||
| sortable = True | ||
| except TypeError: | ||
| items = list(iterable) |
Contributor
There was a problem hiding this comment.
This doesn't work with an iterator, does it? The sorted consumes it and then list wont find anything. Better read it into a list first and then try .sort().
Contributor
Author
There was a problem hiding this comment.
Spot on. Indeed it doesn't. I've fixed this now. Shoud've checked this message first - thanks though.
pochmann3
reviewed
May 2, 2024
more_itertools/more.py
Outdated
|
|
||
| # Sets are unordered. Could use list(dict.fromkeys(items)) | ||
| # if every item was Hashable. | ||
| # This is suboptimal, but both functions above are already O(n^2) |
Contributor
There was a problem hiding this comment.
What's O(n^2)? The permuting functions? Certainly not, as there are usually more than quadratically many permutations.
Contributor
Author
There was a problem hiding this comment.
_full and _partial. I've not looked at them in detail, I just noticed they both contained 2 or 3 for loops (in sequence) within a while loop. If the while loop requires longer than O(n) before it breaks, then yes it is slower than O(n^2).
I can change it to "at best O(n^2)" if you like? The point of that comment still stands: using O(n) sequential look up instead of an O(1) hash table for the n items, does not make things subtantially slower than it would be already
Contributor
There was a problem hiding this comment.
I'd say "are already worse than O(n^2)".
.........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................C:\Users\drjam\Coding\repos\more-itertools\more_itertools\more.py:1712: DeprecationWarning: zip_equal will be removed in a future version of more-itertools. Use the builtin zip function with strict=True instead. warnings.warn( ...............................................................................................................................................................................................................................s..................................................... ---------------------------------------------------------------------- Ran 781 tests in 3.152s OK (skipped=1)
\more-itertools>python -m unittest .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................\more-itertools\more_itertools\more.py:1705: DeprecationWarning: zip_equal will be removed in a future version of more-itertools. Use the builtin zip function with strict=True instead. warnings.warn( ...............................................................................................................................................................................................................................s..................................................... ---------------------------------------------------------------------- Ran 781 tests in 4.959s OK (skipped=1)
… test, not just 1==True.
…are an index. e.g. 1==True
Cycles not dict
Collaborator
|
Checking in on this... the TODO in the test cases, is that still pending? |
Contributor
Author
|
@bbayles Well spotted. I think it's better as @pochmann3 says to make no promises regarding the order of permutations. I was just erring on the side of caution after I noticed the tests I added were set() == set(). The existing tests are sorted(set(permutations())) == sorted(distinct_permutations()) however, so aren't testing the actual order the permutations are yielded in either. |
parthea
referenced
this pull request
in googleapis/google-cloud-python
Aug 26, 2024
[](https://renovatebot.com) This PR contains the following updates: | Package | Change | Age | Adoption | Passing | Confidence | |---|---|---|---|---|---| | [cachetools](https://togithub.com/tkem/cachetools) | `==5.4.0` -> `==5.5.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [cffi](http://cffi.readthedocs.org) ([source](https://togithub.com/python-cffi/cffi), [changelog](https://cffi.readthedocs.io/en/latest/whatsnew.html)) | `==1.16.0` -> `==1.17.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [google-auth](https://togithub.com/googleapis/google-auth-library-python) | `==2.32.0` -> `==2.34.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [idna](https://togithub.com/kjd/idna) ([changelog](https://togithub.com/kjd/idna/blob/master/HISTORY.rst)) | `==3.7` -> `==3.8` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [importlib-metadata](https://togithub.com/python/importlib_metadata) | `==8.2.0` -> `==8.4.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [jaraco-context](https://togithub.com/jaraco/jaraco.context) | `==5.3.0` -> `==6.0.1` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [keyring](https://togithub.com/jaraco/keyring) | `==25.2.1` -> `==25.3.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [more-itertools](https://togithub.com/more-itertools/more-itertools) | `==10.3.0` -> `==10.4.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | | [zipp](https://togithub.com/jaraco/zipp) | `==3.19.2` -> `==3.20.0` | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | [](https://docs.renovatebot.com/merge-confidence/) | --- ### Release Notes <details> <summary>tkem/cachetools (cachetools)</summary> ### [`v5.5.0`](https://togithub.com/tkem/cachetools/blob/HEAD/CHANGELOG.rst#v550-2024-08-18) [Compare Source](https://togithub.com/tkem/cachetools/compare/v5.4.0...v5.5.0) \=================== - `TTLCache.expire()` returns iterable of expired `(key, value)` pairs. - `TLRUCache.expire()` returns iterable of expired `(key, value)` pairs. - Documentation improvements. - Update CI environment. </details> <details> <summary>python-cffi/cffi (cffi)</summary> ### [`v1.17.0`](https://togithub.com/python-cffi/cffi/releases/tag/v1.17.0) [Compare Source](https://togithub.com/python-cffi/cffi/compare/v1.16.0...v1.17.0) - Add support for Python 3.13. - Free-threaded CPython builds (i.e. `python3.13t` and the `3.13t` ABI) are not currently supported. - In API mode, when you get a function from a C library by writing `fn = lib.myfunc`, you get an object of a special type for performance reasons, instead of a `<cdata 'C-function-type'>`. Before version 1.17 you could only call such objects. You could write `ffi.addressof(lib, "myfunc")` in order to get a real `<cdata>` object, based on the idea that in these cases in C you'd usually write `&myfunc` instead of `myfunc`. In version 1.17, the special object `lib.myfunc` can now be passed in many places where CFFI expects a regular `<cdata>` object. For example, you can now pass it as a callback to a C function call, or write it inside a C structure field of the correct pointer-to-function type, or use `ffi.cast()` or `ffi.typeof()` on it. **Full Changelog**: python-cffi/cffi@v1.16.0...v1.17.0 </details> <details> <summary>googleapis/google-auth-library-python (google-auth)</summary> ### [`v2.34.0`](https://togithub.com/googleapis/google-auth-library-python/blob/HEAD/CHANGELOG.md#2340-2024-08-13) [Compare Source](https://togithub.com/googleapis/google-auth-library-python/compare/v2.33.0...v2.34.0) ##### Features - **auth:** Update get_client_ssl_credentials to support X.509 workload certs ([#​1558](https://togithub.com/googleapis/google-auth-library-python/issues/1558)) ([18c2ec1](https://togithub.com/googleapis/google-auth-library-python/commit/18c2ec1b571d506c0dbcffc483aa5e7b95e1b246)) ##### Bug Fixes - Retry token request on retryable status code ([#​1563](https://togithub.com/googleapis/google-auth-library-python/issues/1563)) ([f858a15](https://togithub.com/googleapis/google-auth-library-python/commit/f858a151cb7e29d34578e03c9e3fd4110c6bc258)) ### [`v2.33.0`](https://togithub.com/googleapis/google-auth-library-python/blob/HEAD/CHANGELOG.md#2330-2024-08-06) [Compare Source](https://togithub.com/googleapis/google-auth-library-python/compare/v2.32.0...v2.33.0) ##### Features - Implement async `StaticCredentials` using access tokens ([#​1559](https://togithub.com/googleapis/google-auth-library-python/issues/1559)) ([dc17dfc](https://togithub.com/googleapis/google-auth-library-python/commit/dc17dfc3fb65c87f2912300f0d11f79781240e78)) - Implement base classes for credentials and request sessions ([#​1551](https://togithub.com/googleapis/google-auth-library-python/issues/1551)) ([036dac4](https://togithub.com/googleapis/google-auth-library-python/commit/036dac43018b8cc26b5608e1bb21d6e3ee62a282)) ##### Bug Fixes - **metadata:** Enhance retry logic for metadata server access in \_metadata.py ([#​1545](https://togithub.com/googleapis/google-auth-library-python/issues/1545)) ([61c2432](https://togithub.com/googleapis/google-auth-library-python/commit/61c24321e52f6e017eecee211e11260d621c909b)) ##### Documentation - Update argument for Credentials initialization ([#​1557](https://togithub.com/googleapis/google-auth-library-python/issues/1557)) ([40b9ed9](https://togithub.com/googleapis/google-auth-library-python/commit/40b9ed91a6b01948561cfc71edaaabdd7f362f17)) </details> <details> <summary>kjd/idna (idna)</summary> ### [`v3.8`](https://togithub.com/kjd/idna/releases/tag/v3.8) [Compare Source](https://togithub.com/kjd/idna/compare/v3.7...v3.8) #### What's Changed - Fix regression where IDNAError exception was not being produced for certain inputs. - Add support for Python 3.13, drop support for Python 3.5 as it is no longer testable. - Documentation improvements - Updates to package testing using Github actions Thanks to Hugo van Kemenade for contributions to this release. **Full Changelog**: kjd/idna@v3.7...v3.8 </details> <details> <summary>python/importlib_metadata (importlib-metadata)</summary> ### [`v8.4.0`](https://togithub.com/python/importlib_metadata/compare/v8.3.0...v8.4.0) [Compare Source](https://togithub.com/python/importlib_metadata/compare/v8.3.0...v8.4.0) ### [`v8.3.0`](https://togithub.com/python/importlib_metadata/compare/v8.2.0...v8.3.0) [Compare Source](https://togithub.com/python/importlib_metadata/compare/v8.2.0...v8.3.0) </details> <details> <summary>jaraco/jaraco.context (jaraco-context)</summary> ### [`v6.0.1`](https://togithub.com/jaraco/jaraco.context/compare/v6.0.0...v6.0.1) [Compare Source](https://togithub.com/jaraco/jaraco.context/compare/v6.0.0...v6.0.1) ### [`v6.0.0`](https://togithub.com/jaraco/jaraco.context/compare/v5.3.0...v6.0.0) [Compare Source](https://togithub.com/jaraco/jaraco.context/compare/v5.3.0...v6.0.0) </details> <details> <summary>jaraco/keyring (keyring)</summary> ### [`v25.3.0`](https://togithub.com/jaraco/keyring/compare/v25.2.1...v25.3.0) [Compare Source](https://togithub.com/jaraco/keyring/compare/v25.2.1...v25.3.0) </details> <details> <summary>more-itertools/more-itertools (more-itertools)</summary> ### [`v10.4.0`](https://togithub.com/more-itertools/more-itertools/releases/tag/v10.4.0): Version 10.4.0 [Compare Source](https://togithub.com/more-itertools/more-itertools/compare/v10.3.0...v10.4.0) ##### What's Changed - Issue 854: sample improvements by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/855](https://togithub.com/more-itertools/more-itertools/pull/855) - Issue 858: Use chain and starmap in run_length.decode by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/861](https://togithub.com/more-itertools/more-itertools/pull/861) - Issue 859: Update totient recipe by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/860](https://togithub.com/more-itertools/more-itertools/pull/860) - Distinct permutations of incomparable items by [@​JamesParrott](https://togithub.com/JamesParrott) in [https://github.com/more-itertools/more-itertools/pull/834](https://togithub.com/more-itertools/more-itertools/pull/834) - Clarify seekable.relative_seek behavior by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/863](https://togithub.com/more-itertools/more-itertools/pull/863) - Issue 864: Improve \_sample_unweighted by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/865](https://togithub.com/more-itertools/more-itertools/pull/865) - Use log1p for \_sample_unweighted by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/868](https://togithub.com/more-itertools/more-itertools/pull/868) - Issue 862: change relative_seek() behaviour by [@​dkrikun](https://togithub.com/dkrikun) in [https://github.com/more-itertools/more-itertools/pull/866](https://togithub.com/more-itertools/more-itertools/pull/866) - Issue 876: is_sorted clarifications by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/877](https://togithub.com/more-itertools/more-itertools/pull/877) - Issue 870: counts parameter for sample by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/875](https://togithub.com/more-itertools/more-itertools/pull/875) - Issue 869: Add a steps argument to circular_shifts by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/874](https://togithub.com/more-itertools/more-itertools/pull/874) - Issue 871: Add a fast path for sliding_window by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/873](https://togithub.com/more-itertools/more-itertools/pull/873) - type annotation of `windowed_complete` corrected by [@​m472](https://togithub.com/m472) in [https://github.com/more-itertools/more-itertools/pull/881](https://togithub.com/more-itertools/more-itertools/pull/881) - \[Docs] Fix strictly_n missing the n parameter by [@​fakuivan](https://togithub.com/fakuivan) in [https://github.com/more-itertools/more-itertools/pull/886](https://togithub.com/more-itertools/more-itertools/pull/886) - Standardize type hints for isinstance's second argument by [@​jbosboom](https://togithub.com/jbosboom) in [https://github.com/more-itertools/more-itertools/pull/887](https://togithub.com/more-itertools/more-itertools/pull/887) - Issue 883: change type hint by [@​akisatoon1](https://togithub.com/akisatoon1) in [https://github.com/more-itertools/more-itertools/pull/884](https://togithub.com/more-itertools/more-itertools/pull/884) - Add type overloads for `zip_broadcast` by [@​Pandede](https://togithub.com/Pandede) in [https://github.com/more-itertools/more-itertools/pull/888](https://togithub.com/more-itertools/more-itertools/pull/888) - Issue 889: Optimize triplewise by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/891](https://togithub.com/more-itertools/more-itertools/pull/891) - Add option `strict` to `sort_together` by [@​Pandede](https://togithub.com/Pandede) in [https://github.com/more-itertools/more-itertools/pull/892](https://togithub.com/more-itertools/more-itertools/pull/892) - Updates for version 10.4.0 by [@​bbayles](https://togithub.com/bbayles) in [https://github.com/more-itertools/more-itertools/pull/893](https://togithub.com/more-itertools/more-itertools/pull/893) ##### New Contributors - [@​JamesParrott](https://togithub.com/JamesParrott) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/834](https://togithub.com/more-itertools/more-itertools/pull/834) - [@​dkrikun](https://togithub.com/dkrikun) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/866](https://togithub.com/more-itertools/more-itertools/pull/866) - [@​m472](https://togithub.com/m472) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/881](https://togithub.com/more-itertools/more-itertools/pull/881) - [@​fakuivan](https://togithub.com/fakuivan) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/886](https://togithub.com/more-itertools/more-itertools/pull/886) - [@​jbosboom](https://togithub.com/jbosboom) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/887](https://togithub.com/more-itertools/more-itertools/pull/887) - [@​akisatoon1](https://togithub.com/akisatoon1) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/884](https://togithub.com/more-itertools/more-itertools/pull/884) - [@​Pandede](https://togithub.com/Pandede) made their first contribution in [https://github.com/more-itertools/more-itertools/pull/888](https://togithub.com/more-itertools/more-itertools/pull/888) **Full Changelog**: more-itertools/more-itertools@v10.3.0...v10.4.0 </details> <details> <summary>jaraco/zipp (zipp)</summary> ### [`v3.20.0`](https://togithub.com/jaraco/zipp/compare/v3.19.3...v3.20.0) [Compare Source](https://togithub.com/jaraco/zipp/compare/v3.19.3...v3.20.0) ### [`v3.19.3`](https://togithub.com/jaraco/zipp/compare/v3.19.2...v3.19.3) [Compare Source](https://togithub.com/jaraco/zipp/compare/v3.19.2...v3.19.3) </details> --- ### Configuration 📅 **Schedule**: Branch creation - "before 4am on Monday" (UTC), Automerge - At any time (no schedule defined). 🚦 **Automerge**: Disabled by config. Please merge this manually once you are satisfied. ♻ **Rebasing**: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox. 👻 **Immortal**: This PR will be recreated if closed unmerged. Get [config help](https://togithub.com/renovatebot/renovate/discussions) if that's undesired. --- - [ ] <!-- rebase-check -->If you want to rebase/retry this PR, check this box --- This PR was generated by [Mend Renovate](https://www.mend.io/free-developer-tools/renovate/). View the [repository job log](https://developer.mend.io/github/googleapis/google-cloud-python). <!--renovate-debug:eyJjcmVhdGVkSW5WZXIiOiIzOC4yNi4xIiwidXBkYXRlZEluVmVyIjoiMzguMjYuMSIsInRhcmdldEJyYW5jaCI6Im1haW4iLCJsYWJlbHMiOltdfQ==--> Co-authored-by: Anthonios Partheniou <partheniou@google.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Issue reference
#832
Changes
Extends distinct_permutations to support iterables whose items cannot form a partial ordering.
Checks and tests