Reducing a set of non-unique elements via transformations

Posted by Andrey Fedorov on Stack Overflow See other posts from Stack Overflow or by Andrey Fedorov
Published on 2010-05-31T18:51:41Z Indexed on 2010/05/31 18:53 UTC
Read the original article Hit count: 274

Filed under:

algorithm

|

algorithm-design

I have:

1) a "starting set" of not-necessarily-unique elements, e.x. { x, y, z, z },

2) a set of transformations, e.x. (x,z) => y, (z,z) => z, x => z, y => x, and

3) a "target set" that I am trying to get by applying transformations to the starting set, e.x. { z }.

I'd like to find an algorithm to generate the (possibly infinite) possible applications of the transformations to the starting set that result in the target set. For example:

{ x, y, z, z }, y => x
{ x, x, z, z }, x => z
{ z, x, z, z }, x => z
{ z, z, z, z }, (z, z) => z
{ z, z, z }, (z, z) => z
{ z, z }, (z, z) => z
{ z }

This sounds like something that's probably an existing (named) problem, but I don't recognize it. Can anyone help me track it down, or suggest further reading on something similar?

© Stack Overflow or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about algorithm-design

Solutions for exercises in The Algorithm Design Manual

as seen on Stack Overflow - Search for 'Stack Overflow'
Does anybody know where to find solutions for the exercises in the book The Algorithm Design Manual? >>> More
Algorithm design, "randomising" timetable schedule in Python although open to other languages.

as seen on Stack Overflow - Search for 'Stack Overflow'
Before I start I should add I am a musician and not a native programmer, this was undertook to make my life easier. Here is the situation, at work I'm given a new csv file each which contains a list of sound files, their length, and the minimum total amount of time they must be played. I create… >>> More
Algorithm for dynamic combinations

as seen on Stack Overflow - Search for 'Stack Overflow'
My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to… >>> More
Disk Search / Sort Algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a Range of numbers say 1 to 10,000, Input is in random order. Constraint: At any point only 1000 numbers can be loaded to memory. Assumption: Assuming unique numbers. I propose the following efficient , "When-Required-sort Algorithm". We write the numbers into files which are designated… >>> More
Dynamic programming practice problems with solutions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is there a website or book that contains practice problems and solutions? Thanks Bala >>> More