Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • May 19 19:34
    stewSquared edited #27
  • May 19 19:34
    stewSquared edited #27
  • May 19 19:33
    stewSquared edited #27
  • May 19 19:32
    stewSquared opened #27
  • Mar 19 00:58
    mcanlas commented #26
  • Mar 19 00:57
    mcanlas synchronize #26
  • Mar 19 00:40
    mcanlas opened #26
  • Mar 18 02:25
    denisrosset opened #25
  • Mar 18 02:24
    denisrosset assigned #24
  • Mar 18 02:24
    denisrosset opened #24
  • Mar 15 19:24
    denisrosset opened #23
  • Feb 04 22:51

    denisrosset on master

    Touch up Grp/FinitelyGeneratedG… (compare)

  • Jan 16 16:25

    denisrosset on master

    Group and Eq on finitely genera… (compare)

  • Dec 20 2018 10:21
    denisrosset opened #22
  • Dec 20 2018 10:15
    denisrosset opened #21
  • Dec 20 2018 10:03
    denisrosset opened #20
  • Dec 20 2018 09:36
    denisrosset opened #19
  • Nov 29 2018 05:03

    denisrosset on v0.16.0.3

    (compare)

  • Nov 29 2018 05:03

    denisrosset on master

    Setting version to 0.16.0.3 Setting version to 0.16.0.4-SNA… (compare)

  • Nov 29 2018 04:57

    denisrosset on master

    Better naming scheme for permut… (compare)

Denis Rosset
@denisrosset
  • should the original list be considered as some kind of alphabet (so unordered, no repetition), or a something which has structure (with possible repetitions)?
  • what is the size of the output? can it, should it be represented as an explicit structure with every element allocated? (which is fine until N > 10000 elements)
  • what are the sequence types supported: Array, Seq, Vector, List? the last two have not so good performance characteristics
  • do we abstract over the sequence type, at the price of crazy CanBuildFrom stuff?
Srepfler Srdan
@schrepfler
right, clearly here the set is very small, the domain I’d like to apply this would be betting on probabilities, in these cases one can have 20-30 elements (so called selections) and not all of them are combinable (all those where there’s some sort of causal relationship, ex. selections on the same event are not combinable as then probability of an event happening would obvously grow if the other one also happend)
I think in these kinds of perms we might actually hit some bigger numbers
and understanding how to invalidate/identify non combinable selections becomes computationally hard
Srepfler Srdan
@schrepfler
in terms of design these are very good questions
the original list is unordered, no repetitions are possible
(ex. I just select a bunch of selections on a site on which I’d like to make a bet, let’s say a selection is just an id 1234 which rapresents some probability that an event might happen or not)
from the point of view of who observes this structure, it’s probably not that important to see all combinations
ex.
if I select 4 selections from 4 separate events
Srepfler Srdan
@schrepfler
that would output 4 singles, 1 accumulator of 4 (all 4 to win), 4 trebles (accumulators made out of 3 selections), 6 doubles (accumulators made out of 2 selections), and then even those can be put together, ex. yankee bet which is that all 6 doubles, 4 trebles, and the four-fold will happen and finally a Luky 15 which consists of 15 bets involving 4 selections in different events. The bet includes 4 singles, 6 doubles, 4 trebles, and 1 fourfold.
but if two of these would have been on the same event, some of these things would be non combinable
in terms of supported collection types I’m not sure, if these things are big perhaps Seq would be better if we can keep things lazy?
Srepfler Srdan
@schrepfler
and then, for some things which are ordered lists are ok, but if something is unordered and without repetitions shouldn’t we look at sets?
Srepfler Srdan
@schrepfler
also, @denisrosset, would it be possible to parallelise some of these calculations on let’s say spark?
are these functions sutable to paralellise
Srepfler Srdan
@schrepfler
(not generally combinatorics, is alasc suitable to run on top of spark)
Denis Rosset
@denisrosset
I don't see why you couldn't run Alasc on top of Spark
The API presented to the user has immutable objects
However, I currently don't have the time to implement all these combinatorics; I guess the only part where Alasc can help is generating permutations of an ordered/unordered list with repetitions; and when the permutation group has structure (i.e. when some permutations are allowed and also some forbidden)
Otherwise, standard combinatoric algorithms will be much faster
Alasc can handle pretty big groups and lists, and can explore permutations under arbitrary groups; it scales well; but it will be slow compared to simpler algorithms
I wrote it to handle a problem with a lot of structure
Denis Rosset
@denisrosset
Think, for example, of the permutations of nodes in a graph/network, that keeps the shape of the graph/network invariant.
Dave Nicponski
@virusdave
hi! stupid question and i apologize if i just didn't see the answer, but are artifacts of this library published on maven or elsewhere?
Denis Rosset
@denisrosset
Yes!
On bintray
Add the repository "bintray/denisrosset/maven" at "https://dl.bintray.com/denisrosset/maven"
Then add the library "net.alasc" %% "alasc-core" % alascVersion
Stewart Stewart
@stewSquared
Hi! I just wanted to say I think this library is really cool.
I stumbled into it after learning about GAP while I was looking for nice ways to model permutation puzzles :)
I take it the GAP documentation is the best place to learn about AlaSc features for the time being?
Denis Rosset
@denisrosset
Not exactly... I built Alasc with slightly different design goals.
If you play with Grp[Perm], everything should be easier. Don't forget to import net.alasc.perms.default._ which selects the appropriate algorithms.
Stewart Stewart
@stewSquared

So! I've been fiddling around with AlaSc for a little while now. I have a few questions:

What is the Cycles type meant to be used for? It seems to be nearly identical to Perm, but with fewer convenient instances.

Is there a (planned) way to derive the direct/semidirect products of groups?

Any interest in porting this to Scala.js? It looks like the java dependencies are minimal, and I'd like to use this in some presentations :)

(I'm also happy to submit PRs for low-hanging fruit, since I find this topic fascinating and have a little free time on my hands)
Denis Rosset
@denisrosset
Hi @stewSquared , that's great!
The only problematic dependency should be metal
https://github.com/denisrosset/metal , as it does weird things with primitive arrays
I'd welcome a JS adapation of both metal and alasc
Denis Rosset
@denisrosset
Regarding the Cycles type: it's there to provide human-readable notation of permutations as a product of cycles. Having a specific data type enables the use of property based tests. However, Cycles is inefficient and should never be used for computations (one could think, for example, that storing a permutation as a product of cycles is more efficient for sparse permutations -- in principle yes, but not here)
Regarding direct product of groups: you can work directly with tuples of permutations, or tuples of any type that has a FaithfulPermutationActionBuilder instance
For semidirect products, the correct API depends probably on the use case; I've never asked myself how the construction should look like in code
**
Regarding Metal, I had a look at the code base, and good lord, it needs a bit of cleanup
The macro-based recovery of singleton values could be handled much better using a shapeless.Witness
Stewart Stewart
@stewSquared

Regarding direct product of groups: you can work directly with tuples of permutations, or tuples of any type that has a FaithfulPermutationActionBuilder instance

Nice! I've played with it a bit now. Pretty handy.
I might try implementing a semidirect product for Group[A] and Group[B] given an automorphism for B. I found this blog post very illuminating: http://www.weddslist.com/groups/building/sdp.html

By the way, I gave a Rubik's Cube Group Theory talk an NEScala, in which I used AlaSc.
It didn't come out very well, so I'm working on V2 and a series of blog posts, but I've been telling people about the library.