Learn to think and write on Erlang (using the example of two combinatorial problems)
- ... Then I give him in the face ... No, you can not beat!
“The fact of the matter is that it is impossible to beat,” Panikovsky sighed hypocritically. - Bender does not allow.
I. Ilf, E. Petrov. Golden calf
Brainworm Braga lived in a transparent vessel and was so
strong that even horror. It is not something from the belly - right from the mouth
rushed to the head and began to throw there from side to side,
breaking mental props and fortifications.
M. Uspensky. Where we are not .
Perhaps everyone who first starts studying Erlang feels that he is in the position of Shura Balaganov, who was forbidden to use the only available and understandable method: “you can't beat ...”. Erlang lacks such familiar concepts for most modern languages as reassignment of a variable and, accordingly, accumulation of the result in one variable. (For the sake of fairness, it should be noted that the behavior of the “global variable variable” type in Erlang can still be implemented. For this, each process has a hash dictionary that stores key-value pairs defined by the programmer. There are built-in functions put (Key, Value), get (Key) and some other auxiliary functions. But using such a dictionary in applications is considered bad style and is recommended only in exceptional cases ( http://www.erlang.org/doc/man/erlang.html\#put-2 )). As a result, iterations in the loop cannot be implemented using the usual incrementing of the values of the iteration variable. The accumulation of the result is carried out only through recursion, and the organization of cycles through tail recursion. (Of course, both iterations and accumulation of the result in a cycle can be implemented through library functions for lists of lists: foreach (Function, List), lists: foldl (Function, StartValue, List), lists: foldr (Function, StartValue, List) ( http : //www.erlang.org/doc/man/lists.html ) and their analogues for collections ( http://www.erlang.org/doc/man/sets.html , http://www.erlang.org /doc/man/ordsets.html , http://www.erlang.org/doc/man/gb_sets.html ) and arrays ( http://www.erlang.org/doc/man/array.html ). But our goal is to learn how to write cycles, and not to use ready-made solutions, so here we will refrain from using such libraries).
')
Thus, in Erlang you have to break the usual patterns of thinking and replace them with new patterns, characteristic only for this programming language. Of course, the ideal remedy is the brainwalk, capable of breaking all “mental props and fortifications.” But for us this is perhaps too radical a means, and we will go a different way.
In the life of St. Anthony the Great there is a story about one of his students. The disciple stood in the temple and listened to St. Anthony reading the Psalter. As soon as the first verse of the first psalm sounded:
the disciple left the temple. Since then, no one has seen him for almost 30 years, and when he reappeared in the temple, Anthony the Great asked why he left them for so long and where he disappeared. The disciple replied: “Father, I heard the words of the psalm, and retired to the wilderness in order to try to fulfill what the words are saying, not to go to the council of unholy thoughts. ” In other words, he learned a practical lesson from these words, and now he has come to read further. Unfortunately, we do not have such a reserve of time, and our goals are not so sublime. But the main concept can be adopted.
We will look at two standard combinatorial tasks:
and analyze various approaches and ways of solving them using the Erlang programming language, in order to understand and master some specific features of programming in this language using concrete examples.
All examples are collected in the module combinat.erl and are available at: https://github.com/raven29/combinat_erl.git
As a solution algorithm, we will use direct recursive enumeration. This means that at each step of the recursion is performed:
In other words, the procedure involves two stages: a looping at a given level of recursion and a transition to the next level. Accordingly, these two targets require a double recursive call. (The algorithm is based on a naive enumeration and, accordingly, requires optimization. However, it is quite suitable for our purposes, because, firstly, due to simplicity and clarity, it makes it easy to illustrate the methods and techniques used, secondly, it applies to both the problems considered with minimal differences, which makes it possible to carry out appropriate comparisons and parallels).
The basic functionality is implemented in the combinat: permuts_out (List, Number) and combinat: combs_out (List, Number) functions, which print, respectively, all permutations and all combinations of the Number length from the List elements. The following is the permuts_out (List, Number) function that prints permutations. This function is called recursively twice: in the 6th line - for looping through, in the 7th line - to go to the next level of recursion. It is in this last call that the result is incremented in the [RemainH | Result] variable, and the elements contained in this result are excluded from the general list that is passed to the next level of recursion. The fourth List argument holds the original list of elements that is required for correct calculation of the remainder only in the case of permutations.
A similar function for combinations differs from the previous function only by a simpler rule for calculating the transferred remainder and the absence of the fourth argument List.
For greater clarity, two recursive calls can be represented by two different functions. The endings in the function names correspond to their assignments: * _iteration — for iterations on the remainder list at a given level of recursion, * _recursion — to move to the next level of recursion.
Perhaps this option can be considered antipattern, due to the excessive bulkiness.
If you want to write a library function, then there is little use from outputting to the standard stream. You need to get the result and pass it in some form to the client code. To accumulate the result in Erlang there are neither global variables nor static fields. Instead, approaches characteristic of functional languages can be used:
Consider each option in detail.
So far, we have done something useful (if outputting the result to a computer screen can be considered a useful thing) in the body of the function, going down to the bottom of the descending recursion. When moving back, the result returned by the function was not used at all. In other words, the upward movement on recursion went “empty”. With this approach, it is impossible to put together all the displayed values, since they are not related to each other. More productive is the use of the result returned by the function when exiting recursion. In this case, the first call to the recursive function can return the entire cumulative result. The modification of the basic functions is given below and includes three points:
The functions permuts_res (List, Number) and combs_res (List, Number) return a list of lists containing, respectively, all permutations and combinations of length Number.
Sometimes it is convenient not to accumulate the result in one collection variable, but to do something useful with each element immediately after its creation. This approach allows you to increase productivity and significantly reduce memory consumption. You can implement it with a callback function, which is passed as an additional argument. The relevant options are listed below.
The variable Callback can be passed the name of any function from a single argument (with an arity of one - according to the terminology of Erlang). For example, you can call the printout of all permutations of the elements [1,2,3] to 2:
A more meaningful use of the callback function is discussed in the next section.
Another way to implement the accumulation of the result of branching recursion in Erlang is to use two threads. One thread is a performer, it launches our program. The other stream is the observer, the recursive function transmits the received results to it. When the executing thread completes its work, the observer flow displays the total result. Important: you cannot use the main stream (supervisor) in which the erl shell is running as an executing thread, since this thread is not destroyed after program execution. It continues to exist until the erl application is unloaded.
Below is the corresponding implementation. Line 3 is set to “exit through the ladder”, which ensures the transmission of a message from the associated process even if it is completed normally. By default, the trap_exit flag is set to false, which means receiving a message from the associated process only in the event of a crash. Line 5 starts (and simultaneously binds) the executing thread. This thread starts the function permuts_clb (or combs_clb), to which the arguments List, Number are passed, as well as the callback function Callback, which passes each single result to an observer process:
Line 6 starts the loop ([]) function with an empty initial value of the total result. This function "listens" to messages from the executing thread. When the next result is received, a recursive loop (Total ++ [Result]) call (line 14) occurs with an argument supplemented by the newly arrived result from the executing thread. Upon completion of the executing thread, a “ladder exit” occurs: a special kind of tuple (line 10) is passed to loop (), through which the common result is output (line 11) and the connection with the executing thread is broken (line 12 ). Supervisor - pid of the observer thread, Worker - pid of the executing thread.
The function is called with permuts_clb or combs_clb as the first argument, depending on the problem being solved. For example, printing of all permutations from elements [1,2,3] through 2 is carried out through a call:
There may be errors characteristic of a beginner. First, you cannot start loop () before spawn_link (). It would seem that it would be more reliable, since the listener function, which was started before the executor thread was launched, will certainly not miss a single message from this stream. But as a result, the process will “hang” on loop (), and the next line will never be called. Secondly, the use of the Supervisor variable to send a message to the observer stream is mandatory: the design
does not work, since the self () function will be executed when called in the executing thread and, accordingly, will receive the pid of the executing thread. Thanks to w495 and EvilBlueBeaver for constructive criticism of these comments (and just for helping us figure it out).
And one more small note: when experimenting with the proc () function, various oddities can occur, for example, the function may begin to produce a result with a “delay”, i.e. with each call to produce the result of the previous call. This may be due to the fact that we are launching the main stream as an observer stream. Therefore, after some failure, the next loop () call will first process all messages from the last call, if any. In this sense, the implementation of the listener stream will also be more reliable in a separate stream generated by the spawn () or spawn_link () function.
Some programming languages have a syntax structure called " list comprehension ". It allows in a compact and elegant form to specify an iterative list traversal, as a result of which a new list is generated, each element of which is obtained from the original list by applying some function to each element of the original list. The construction is based on the notation of mathematical set theory. So, for example, in the list comprehension construction, the output of squares of all integers from 1 to 9 looks like:
In list comprehension it is also possible to transmit several lists and impose conditions. As an example, consider the output of the multiplication table from 1 to 9:
as well as multiplication tables, in which repeated results with the transposition of factors are excluded:
In the Russian-language literature, “list comprehension” is translated as “inclusion of lists”, “generation of lists”. The main meaning of the translation of “comprehension” is “to comprehend”, “to understand”. So, to understand English is to include.
It should be noted that the comprehension construct exists not only for lists, but also for collections of other types. Erlang has list comprehension and binary comprehension .
In the list comprehension construction, you can specify an iterative list traversal; as a result, the basic function takes the form:
The permuts_comp function calls itself recursively from list comprehension.
This is perhaps the most elegant permutation function of all possible.
The generalization of the previous result on the function of combinations, unfortunately, is not so obvious. The fact is that in list comprehension in this case it is necessary to transfer not the entire list, but only the remainder determined by the number from the previous call. If instead of lists there was an array, one could easily calculate the necessary index. But arrays are not in the basic types of Erlang. It is necessary either to use the array library, or to organize the array "manually".
This turns out to be quite simple, and the corresponding implementation is presented below. From the source List, we build a list of ListIndexed tuples, each element of which contains the elements of the source list and an integer index (line 2). For such a conversion, the function lists: zip (List1, List2) from the standard module lists. When displaying the result, we use the function lists: unzip (ListIndexed), which returns the initial view without indexes to the indexed list (line 5). And most importantly - in list comprehension, you can now easily specify the required limit on the indices included in the iterations (line 11).
It looks somewhat awkward, and this is the only program among our examples in which we had to resort to library functions lists: zip (List1, List2), lists: unzip (ListTuple), lists: seq (StartValue, Length). This attempt can also be considered a sample of the anti-pattern, since for the task at hand, it would be more consistent to use the array module, but this will be another story ...
“The fact of the matter is that it is impossible to beat,” Panikovsky sighed hypocritically. - Bender does not allow.
I. Ilf, E. Petrov. Golden calf
Brainworm Braga lived in a transparent vessel and was so
strong that even horror. It is not something from the belly - right from the mouth
rushed to the head and began to throw there from side to side,
breaking mental props and fortifications.
M. Uspensky. Where we are not .
Perhaps everyone who first starts studying Erlang feels that he is in the position of Shura Balaganov, who was forbidden to use the only available and understandable method: “you can't beat ...”. Erlang lacks such familiar concepts for most modern languages as reassignment of a variable and, accordingly, accumulation of the result in one variable. (For the sake of fairness, it should be noted that the behavior of the “global variable variable” type in Erlang can still be implemented. For this, each process has a hash dictionary that stores key-value pairs defined by the programmer. There are built-in functions put (Key, Value), get (Key) and some other auxiliary functions. But using such a dictionary in applications is considered bad style and is recommended only in exceptional cases ( http://www.erlang.org/doc/man/erlang.html\#put-2 )). As a result, iterations in the loop cannot be implemented using the usual incrementing of the values of the iteration variable. The accumulation of the result is carried out only through recursion, and the organization of cycles through tail recursion. (Of course, both iterations and accumulation of the result in a cycle can be implemented through library functions for lists of lists: foreach (Function, List), lists: foldl (Function, StartValue, List), lists: foldr (Function, StartValue, List) ( http : //www.erlang.org/doc/man/lists.html ) and their analogues for collections ( http://www.erlang.org/doc/man/sets.html , http://www.erlang.org /doc/man/ordsets.html , http://www.erlang.org/doc/man/gb_sets.html ) and arrays ( http://www.erlang.org/doc/man/array.html ). But our goal is to learn how to write cycles, and not to use ready-made solutions, so here we will refrain from using such libraries).
')
Thus, in Erlang you have to break the usual patterns of thinking and replace them with new patterns, characteristic only for this programming language. Of course, the ideal remedy is the brainwalk, capable of breaking all “mental props and fortifications.” But for us this is perhaps too radical a means, and we will go a different way.
In the life of St. Anthony the Great there is a story about one of his students. The disciple stood in the temple and listened to St. Anthony reading the Psalter. As soon as the first verse of the first psalm sounded:
, ...
the disciple left the temple. Since then, no one has seen him for almost 30 years, and when he reappeared in the temple, Anthony the Great asked why he left them for so long and where he disappeared. The disciple replied: “Father, I heard the words of the psalm, and retired to the wilderness in order to try to fulfill what the words are saying, not to go to the council of unholy thoughts. ” In other words, he learned a practical lesson from these words, and now he has come to read further. Unfortunately, we do not have such a reserve of time, and our goals are not so sublime. But the main concept can be adopted.
We will look at two standard combinatorial tasks:
- search for all possible permutations (permutations) from a given set of N elements
- search for all possible combinations (combinations) of a given set of N elements
and analyze various approaches and ways of solving them using the Erlang programming language, in order to understand and master some specific features of programming in this language using concrete examples.
All examples are collected in the module combinat.erl and are available at: https://github.com/raven29/combinat_erl.git
Two goals - two recursions
As a solution algorithm, we will use direct recursive enumeration. This means that at each step of the recursion is performed:
- cycling through all possible values from the list and adding each of these values to existing results;
- a recursive call with the transfer of a new list, from which already used values are excluded.
In other words, the procedure involves two stages: a looping at a given level of recursion and a transition to the next level. Accordingly, these two targets require a double recursive call. (The algorithm is based on a naive enumeration and, accordingly, requires optimization. However, it is quite suitable for our purposes, because, firstly, due to simplicity and clarity, it makes it easy to illustrate the methods and techniques used, secondly, it applies to both the problems considered with minimal differences, which makes it possible to carry out appropriate comparisons and parallels).
Base implementation
The basic functionality is implemented in the combinat: permuts_out (List, Number) and combinat: combs_out (List, Number) functions, which print, respectively, all permutations and all combinations of the Number length from the List elements. The following is the permuts_out (List, Number) function that prints permutations. This function is called recursively twice: in the 6th line - for looping through, in the 7th line - to go to the next level of recursion. It is in this last call that the result is incremented in the [RemainH | Result] variable, and the elements contained in this result are excluded from the general list that is passed to the next level of recursion. The fourth List argument holds the original list of elements that is required for correct calculation of the remainder only in the case of permutations.
permuts_out(List, Number) -> permuts_out(List, [], Number, List). permuts_out(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_out([], _Result, _Number, _List) -> ok; permuts_out([RemainH|RemainT], Result, Number, List) -> permuts_out(RemainT, Result, Number, List), permuts_out(List -- [RemainH|Result], [RemainH|Result], Number, List).
A similar function for combinations differs from the previous function only by a simpler rule for calculating the transferred remainder and the absence of the fourth argument List.
combs_out(List, Number) -> combs_out(List, [], Number). combs_out(_Remain, Result, Number) when length(Result) == Number -> io:format("~w~n", [Result]); combs_out([], _Result, _Number) -> ok; combs_out([RemainH|RemainT], Result, Number) -> combs_out(RemainT, Result, Number), combs_out(RemainT, [RemainH|Result], Number).
Two recursions - two functions
For greater clarity, two recursive calls can be represented by two different functions. The endings in the function names correspond to their assignments: * _iteration — for iterations on the remainder list at a given level of recursion, * _recursion — to move to the next level of recursion.
permuts_out_2(List, Number) -> permuts_out_iteration(List, [], Number, List). permuts_out_iteration([], _Result, _Number, _List) -> ok; permuts_out_iteration([RemainH|RemainT], Result, Number, List) -> permuts_out_iteration(RemainT, Result, Number, List), permuts_out_recursion(List -- [RemainH|Result], [RemainH|Result], Number, List). permuts_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_out_recursion(Remain, Result, Number, List) -> permuts_out_iteration(Remain, Result, Number, List). combs_out_2(List, Number) -> combs_out_iteration(List, [], Number, List). combs_out_iteration([], _Result, _Number, _List) -> ok; combs_out_iteration([RemainH|RemainT], Result, Number, List) -> combs_out_iteration(RemainT, Result, Number, List), combs_out_recursion(RemainT, [RemainH|Result], Number, List). combs_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); combs_out_recursion(Remain, Result, Number, List) -> combs_out_iteration(Remain, Result, Number, List).
Perhaps this option can be considered antipattern, due to the excessive bulkiness.
Show the result!
If you want to write a library function, then there is little use from outputting to the standard stream. You need to get the result and pass it in some form to the client code. To accumulate the result in Erlang there are neither global variables nor static fields. Instead, approaches characteristic of functional languages can be used:
- return values in ascending recursion
- callback function
- thread executor and thread accumulator
Consider each option in detail.
Bear there - bear back
So far, we have done something useful (if outputting the result to a computer screen can be considered a useful thing) in the body of the function, going down to the bottom of the descending recursion. When moving back, the result returned by the function was not used at all. In other words, the upward movement on recursion went “empty”. With this approach, it is impossible to put together all the displayed values, since they are not related to each other. More productive is the use of the result returned by the function when exiting recursion. In this case, the first call to the recursive function can return the entire cumulative result. The modification of the basic functions is given below and includes three points:
- returning the result [Result] instead of outputting to the standard stream (line 3, 11)
- the initial value is returned at the bottom of the recursion - an empty list [] instead of the atom “ok” (line 4, 12)
- accumulation of the result by summing the lists "++" instead of a sequential call (line 6, 14)
The functions permuts_res (List, Number) and combs_res (List, Number) return a list of lists containing, respectively, all permutations and combinations of length Number.
permuts_res(List, Number) -> permuts_res(List, [], Number, List). permuts_res(_Remain, Result, Number, _List) when length(Result) == Number -> [Result]; permuts_res([], _Result, _Number, _List) -> []; permuts_res([RemainH|RemainT], Result, Number, List) -> permuts_res(RemainT, Result, Number, List) ++ permuts_res(List -- [RemainH|Result], [RemainH|Result], Number, List). combs_res(List, Number) -> combs_res(List, [], Number). combs_res(_Remain, Result, Number) when length(Result) == Number -> [Result]; combs_res([], _Result, _Number) -> []; combs_res([RemainH|RemainT], Result, Number) -> combs_res(RemainT, Result, Number) ++ combs_res(RemainT, [RemainH|Result], Number).
And do with it what you want!
Sometimes it is convenient not to accumulate the result in one collection variable, but to do something useful with each element immediately after its creation. This approach allows you to increase productivity and significantly reduce memory consumption. You can implement it with a callback function, which is passed as an additional argument. The relevant options are listed below.
permuts_clb(List, Number, Callback) -> permuts_clb(List, [], Number, List, Callback). permuts_clb(_Remain, Result, Number, _List, Callback) when length(Result) == Number -> Callback(Result); permuts_clb([], _Result, _Number, _List, _Callback) -> ok; permuts_clb([RemainH|RemainT], Result, Number, List, Callback) -> permuts_clb(RemainT, Result, Number, List, Callback), permuts_clb(List -- [RemainH|Result], [RemainH|Result], Number, List, Callback). combs_clb(List, Number, Callback) -> combs_clb(List, [], Number, Callback). combs_clb(_Remain, Result, Number, Callback) when length(Result) == Number -> Callback(Result); combs_clb([], _Result, _Number, _Callback) -> ok; combs_clb([RemainH|RemainT], Result, Number, Callback) -> combs_clb(RemainT, Result, Number, Callback), combs_clb(RemainT, [RemainH|Result], Number, Callback).
The variable Callback can be passed the name of any function from a single argument (with an arity of one - according to the terminology of Erlang). For example, you can call the printout of all permutations of the elements [1,2,3] to 2:
combinat:permuts_clb([1,2,3], 2, fun(X)->io:format("~w~n",[X]) end).
A more meaningful use of the callback function is discussed in the next section.
Big Brother is watching you
Another way to implement the accumulation of the result of branching recursion in Erlang is to use two threads. One thread is a performer, it launches our program. The other stream is the observer, the recursive function transmits the received results to it. When the executing thread completes its work, the observer flow displays the total result. Important: you cannot use the main stream (supervisor) in which the erl shell is running as an executing thread, since this thread is not destroyed after program execution. It continues to exist until the erl application is unloaded.
Below is the corresponding implementation. Line 3 is set to “exit through the ladder”, which ensures the transmission of a message from the associated process even if it is completed normally. By default, the trap_exit flag is set to false, which means receiving a message from the associated process only in the event of a crash. Line 5 starts (and simultaneously binds) the executing thread. This thread starts the function permuts_clb (or combs_clb), to which the arguments List, Number are passed, as well as the callback function Callback, which passes each single result to an observer process:
fun(R)->Supervisor!R end
Line 6 starts the loop ([]) function with an empty initial value of the total result. This function "listens" to messages from the executing thread. When the next result is received, a recursive loop (Total ++ [Result]) call (line 14) occurs with an argument supplemented by the newly arrived result from the executing thread. Upon completion of the executing thread, a “ladder exit” occurs: a special kind of tuple (line 10) is passed to loop (), through which the common result is output (line 11) and the connection with the executing thread is broken (line 12 ). Supervisor - pid of the observer thread, Worker - pid of the executing thread.
%% Function = permuts_clb | combs_clb proc(Function, List, Number) -> process_flag(trap_exit, true), Supervisor = self(), spawn_link(combinat, Function, [List, Number, fun(R)->Supervisor!R end]), loop([]). loop(Total) -> receive {'EXIT', Worker, normal} -> io:format("~w~n", [Total]), unlink(Worker); Result -> loop(Total ++ [Result]) end.
The function is called with permuts_clb or combs_clb as the first argument, depending on the problem being solved. For example, printing of all permutations from elements [1,2,3] through 2 is carried out through a call:
combinat:proc(permuts_clb, [1,2,3], 2).
There may be errors characteristic of a beginner. First, you cannot start loop () before spawn_link (). It would seem that it would be more reliable, since the listener function, which was started before the executor thread was launched, will certainly not miss a single message from this stream. But as a result, the process will “hang” on loop (), and the next line will never be called. Secondly, the use of the Supervisor variable to send a message to the observer stream is mandatory: the design
self()!R
does not work, since the self () function will be executed when called in the executing thread and, accordingly, will receive the pid of the executing thread. Thanks to w495 and EvilBlueBeaver for constructive criticism of these comments (and just for helping us figure it out).
And one more small note: when experimenting with the proc () function, various oddities can occur, for example, the function may begin to produce a result with a “delay”, i.e. with each call to produce the result of the previous call. This may be due to the fact that we are launching the main stream as an observer stream. Therefore, after some failure, the next loop () call will first process all messages from the last call, if any. In this sense, the implementation of the listener stream will also be more reliable in a separate stream generated by the spawn () or spawn_link () function.
To understand is to turn on.
Some programming languages have a syntax structure called " list comprehension ". It allows in a compact and elegant form to specify an iterative list traversal, as a result of which a new list is generated, each element of which is obtained from the original list by applying some function to each element of the original list. The construction is based on the notation of mathematical set theory. So, for example, in the list comprehension construction, the output of squares of all integers from 1 to 9 looks like:
[X*X || X <- [1,2,3,4,5,6,7,8,9]].
In list comprehension it is also possible to transmit several lists and impose conditions. As an example, consider the output of the multiplication table from 1 to 9:
[io:format("~w * ~w = ~w~n", [I, J, I*J]) || I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9]].
as well as multiplication tables, in which repeated results with the transposition of factors are excluded:
[io:format("~w * ~w = ~w~n", [I, J, I*J]) || I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9], I < J].
In the Russian-language literature, “list comprehension” is translated as “inclusion of lists”, “generation of lists”. The main meaning of the translation of “comprehension” is “to comprehend”, “to understand”. So, to understand English is to include.
It should be noted that the comprehension construct exists not only for lists, but also for collections of other types. Erlang has list comprehension and binary comprehension .
The most elegant of its kind
In the list comprehension construction, you can specify an iterative list traversal; as a result, the basic function takes the form:
permuts_comp(List, Number) -> permuts_comp(List, [], Number). permuts_comp(_Remain, Result, Number) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_comp(Remain, Result, Number) -> [permuts_comp(Remain -- [R], [R] ++ Result, Number) || R <- Remain].
The permuts_comp function calls itself recursively from list comprehension.
This is perhaps the most elegant permutation function of all possible.
If you can not, but really want ...
The generalization of the previous result on the function of combinations, unfortunately, is not so obvious. The fact is that in list comprehension in this case it is necessary to transfer not the entire list, but only the remainder determined by the number from the previous call. If instead of lists there was an array, one could easily calculate the necessary index. But arrays are not in the basic types of Erlang. It is necessary either to use the array library, or to organize the array "manually".
This turns out to be quite simple, and the corresponding implementation is presented below. From the source List, we build a list of ListIndexed tuples, each element of which contains the elements of the source list and an integer index (line 2). For such a conversion, the function lists: zip (List1, List2) from the standard module lists. When displaying the result, we use the function lists: unzip (ListIndexed), which returns the initial view without indexes to the indexed list (line 5). And most importantly - in list comprehension, you can now easily specify the required limit on the indices included in the iterations (line 11).
combs_comp(List, Number) -> ListIndexed = lists:zip(List, lists:seq(1, length(List))), combs_comp(ListIndexed, [], Number). combs_comp(_Remain, Result, Number) when length(Result) == Number -> {ResultValue, _I} = lists:unzip(Result), io:format("~w~n", [ResultValue]); combs_comp(Remain, [], Number) -> [combs_comp(Remain -- [R], [R], Number) || R <- Remain]; combs_comp(Remain, [{HValue,HIndex}|T], Number) -> [combs_comp(Remain -- [{R,I}], [{R,I}] ++ [{HValue,HIndex}|T], Number) || {R,I} <- Remain, I > HIndex].
It looks somewhat awkward, and this is the only program among our examples in which we had to resort to library functions lists: zip (List1, List2), lists: unzip (ListTuple), lists: seq (StartValue, Length). This attempt can also be considered a sample of the anti-pattern, since for the task at hand, it would be more consistent to use the array module, but this will be another story ...
Source: https://habr.com/ru/post/157583/
All Articles